所用代码 java

下一个更大元素 II LeetCode 503

题目链接：下一个更大元素 II LeetCode 503 - 中等

思路

两个数组类似拼接起来，循环两遍。

第一种思路：开辟一个新的数组，把值赋值过去，就是长度为2*length。

第二种思路：用取模的方法，遍历两遍。除了本题，其他题也可以用取模的方法来实现成环的操作。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int[] result = new int[nums.length];
        Arrays.fill(result,-1);
        stack.push(0);
        for (int i = 1; i < nums.length * 2; i++) {
            // 取模保证下标都是在result数组里面
            int index = i % nums.length;
            while (!stack.isEmpty() && nums[index] > nums[stack.peek()]){
                result[stack.peek()] = nums[index];
                stack.pop();
            }
            stack.push(index);
        }
        return result;
    }
}

总结

在做这道题的时候，我想到了打家劫舍成环的操作，打家劫舍是两两不能挨着，所以可以不偷最后一家、不偷第一家以及两边都不偷然后取最大值，如果像这样直接连起来的话偷了最后一家不能保证和第二家有没有相连。而本题不要考虑那些，其实就是一个单调栈的问题，只需要把数组拼接起来，然后遍历的时候取模操作就可以了，像这种成环的题都可以使用取模操作来解决。

接雨水 LeetCode 42

题目链接：接雨水 LeetCode 42 - 困难

思路

无。

接雨水需要找的是左边第一个比他大的元素和右边第一个比他大的元素，利用单调栈来对每一行进行计算雨水的量。栈顶元素就是中间的元素，下一个遍历的元素比它大就是右边第一个比他大的元素，左边第一个比他大的元素已经存在的栈里面。

class Solution {
    public int trap(int[] height) {
        int result = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]){
                int mid = height[stack.pop()];
                if (!stack.isEmpty()){
                    // 高度为左右两边较小者减去中间本身
                    int h = Math.min(height[i], height[stack.peek()]) - mid;
                    // 求行宽度需排除自己，就多-1
                    int w = i - stack.peek() - 1;
                    result += h * w;
                }
            }
            stack.push(i);
        }
        return result;
    }
}

总结

本题是单调栈的一个具体运用，我们不仅要求比当前元素第一个大的数，还有找到左边第一个大的值，相当于找两边比当前大的值，然后把该点雨水装满，再判断下一个位置。对于重复的元素我们放入栈和不放入栈效果是一样的，因为找到右边第一个比自己大的后，在栈中我们的元素是单调递增的，第二个元素一样的话结果只是多进行异步计算。

另外，暴力也比较方便，同样也是找左右最高的柱子，但是内我们是按列计算的，一列一列的填充：

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 第一个柱子和最后一个柱子不装雨水，就直接跳过
            if (i==0 || i==height.length-1) continue;
            int lHeight = height[i]; // 记录左边最高的柱子
            int rHeight = height[i]; // 记录右边最高的柱子
            // 找到左边最高的柱子
            for (int j = i-1; j >=0; j--) {
                if (height[j] > lHeight) lHeight = height[j];
            }
            // 找到右边最高的柱子
            for (int j = i+1; j < height.length; j++) {
                if (height[j] > rHeight) rHeight = height[j];
            }
            // 左右最高柱子的最小值减本身柱子就是能装雨水的量（按列计算，行为1）
            int mid = Math.min(lHeight,rHeight) - height[i];
            sum += mid * 1;
        }
        return sum;
    }
}

暴力优化（用一个数组把每个值左右最高高度给记录下来，空间换时间）：

class Solution {
    public int trap(int[] height) {
        if (height.length <= 2) return 0;
        int sum = 0;
        int len = height.length;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
​
        // 记录当前元素左边最大的数
        leftMax[0] = height[0];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
​
        // 记录当前元素右边最大的数
        rightMax[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }
        
        // 求和
        for (int i = 0; i < len; i++) {
            // 中间可接雨水的高度为两边高度的最小值减自己的高度
            int mid = Math.min(leftMax[i], rightMax[i]) - height[i];
            sum += mid;
        }
        return sum;
    }
}