下一個(gè)排列(https://leetcode-cn.com/problems/next-permutation/)

實(shí)現(xiàn)獲取下一個(gè)排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個(gè)更大的排列。
如果不存在下一個(gè)更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。
必須原地修改，只允許使用額外常數(shù)空間。
以下是一些例子，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

找規(guī)律
對(duì)于任何題目，可以找一個(gè)簡(jiǎn)單的例子，然后手動(dòng)列舉出所有的情況，也許可以從中找出規(guī)律。

從上面的例子中可以看出：
1）找到被換的數(shù)的位置：從后往前遍歷數(shù)組，找到第一對(duì)num[i] > num[i-1]的數(shù)，其中i-1這個(gè)位置的數(shù)是被換的數(shù)。
2）找到替換的數(shù)的位置：這個(gè)位置的數(shù)該填誰(shuí)？從end_{i，找到第一個(gè)大于num[i-1]的數(shù)，與其交換位置即可；因?yàn)閺膃nd}i是單調(diào)遞增的，所以第一個(gè)大于num[i-1]的數(shù)是最小的一個(gè)；
3）交換位置后，從i~end位置的數(shù)，剛好為降序序列；將其改成升序序列即可；
4）如果沒(méi)有找到任何num[i]>num[i-1]的對(duì)，那么即為排列的最后一個(gè)，此時(shí)我們需要返回排列的第一個(gè)，即將整個(gè)降序序列改成升序序列即可。
代碼如下：

public static void nextPermutation(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                // len-1 -> i 找到第一個(gè)大于nums[i-1]的數(shù), 與其交換
                int index = nums.length - 1;
                while (nums[index] <= nums[i - 1]){
                    index--;
                }
                swapRef(nums, i - 1, index);
                // len-1 -> i 倒序變正序
                reverse(nums, i, nums.length - 1);
                return;
            }
        }
        reverse(nums, 0, nums.length - 1);
    }

    public static void swapRef(int[] nums, int ind1, int ind2) {
        int temp = nums[ind1];
        nums[ind1] = nums[ind2];
        nums[ind2] = temp;
    }

    public static void reverse(int[] nums, int start, int end){
        for (int i = start, j = end; i < j; i++, j--) {
            swapRef(nums, i, j);
        }
    }

下一個(gè)更大元素 III

    public int nextGreaterElement(int n) {
        char[] nums = String.valueOf(n).toCharArray();
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                int j = nums.length - 1;
                while (nums[j] <= nums[i]) {
                    j--;
                }
                swap(nums, i, j);
                reverse(nums, i + 1, nums.length - 1);
                Long potential = Long.valueOf(new String(nums));
                return potential > Integer.MAX_VALUE ? -1 : Integer.valueOf(new String(nums));
            }
        }
        return -1;
    }

    public void swap(char[] nums, int ind1, int ind2) {
        char temp = nums[ind1];
        nums[ind1] = nums[ind2];
        nums[ind2] = temp;
    }

    public void reverse(char[] nums, int start, int end) {
        int L = start;
        int R = end;
        while (L < R) {
            swap(nums, L, R);
            L++;
            R--;
        }
    }

最佳觀光組合

 public int maxScoreSightseeingPair(int[] A) {
        int maxScore = 0;
        int add = A[0] + 0;
        for (int j = 1; j < A.length; j++) {
            int sub = A[j] - j;
            maxScore = Math.max(maxScore, add + sub);
            add = Math.max(add, A[j] + j); // 因?yàn)楹竺婷總€(gè)sub都是固定的, 所以add只需要選最大的即可
        }
        return maxScore;
    }