class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int res = Math.min(height[left] , height[right]) * (right  - left);
        while(left < right){
            int min = Math.min(height[left], height[right]);
            while(height[right] <= min && left < right){
                right--;
            }
            while(height[left] <= min && left < right){
                left++;
            }
            res  = res > (right - left)*Math.min(height[left], height[right]) ? res : (right - left)*Math.min(height[left], height[right]);

        }
        return res;
    }
}

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        int len = nums.length;
        for (int i = 0; i < len - 1;) {
            int max = -1;
            int nexPos = -1;
            for (int j = nums[i]; j >= 1; j--) {
                if(i + j >= len - 1){return ++res;}
                int nextNum = nums[i + j];
                if(j + nextNum >= max){
                   max = j + nextNum;
                   nexPos = i + j;
                }
            }
            i = nexPos;
            res++;
        }
        return res;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int k = 0;
        for(int i = 0; i < nums.length; i++) {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }
}

dp[0][0] = 0; // 没买入
dp[1][0] = -prices[0]; // 买入

class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int res = 0;
        for (int price : prices) {
            if (price < min) {
                min = price;
            } else if (price - min > res) {
                res = price - min;
            }
        }
        return res;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length;
    int spare = 0;
    int minSpare = Integer.MAX_VALUE;
    int minIndex = 0;

    for (int i = 0; i < len; i++) {
        spare += gas[i] - cost[i];
        if (spare <= minSpare) {
            minSpare = spare;
            minIndex = i;
        }
    }

    return spare < 0 ? -1 : (minIndex + 1) % len;
    }
}

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for(int i = 1; i < ratings.length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        int[] ints = Arrays.copyOfRange(nums, nums.length - k,nums.length);
        int[] ints1 = Arrays.copyOfRange(nums, 0, nums.length - k);
        for (int i = 0; i < nums.length; i++) {
            if(i < ints.length){
                nums[i] = ints[i];
            }else {
                nums[i] = ints1[i - ints.length];
            }
        }
    }
}