数组，找规律

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

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

找规律
对于任何题目，可以找一个简单的例子，然后手动列举出所有的情况，也许可以从中找出规律。

从上面的例子中可以看出：
1）找到被换的数的位置：从后往前遍历数组，找到第一对num[i] > num[i-1]的数，其中i-1这个位置的数是被换的数。
2）找到替换的数的位置：这个位置的数该填谁？从end_{i，找到第一个大于num[i-1]的数，与其交换位置即可；因为从end}i是单调递增的，所以第一个大于num[i-1]的数是最小的一个；
3）交换位置后，从i~end位置的数，刚好为降序序列；将其改成升序序列即可；
4）如果没有找到任何num[i]>num[i-1]的对，那么即为排列的最后一个，此时我们需要返回排列的第一个，即将整个降序序列改成升序序列即可。
代码如下：

public static void nextPermutation(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                // len-1 -> i 找到第一个大于nums[i-1]的数, 与其交换
                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);
        }
    }

下一个更大元素 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); // 因为后面每个sub都是固定的, 所以add只需要选最大的即可
        }
        return maxScore;
    }