算法训练Day59|● 503.下一个更大元素II ● 42. 接雨水

// 暴力求解：创建新数组是原数组的二倍，使得其能模拟循环一圈的场景。双层for循环遍历将符合条件的取模加入结果中。
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] nums1 = new int[2 * nums.length];
        for (int i = 0; i < nums.length; i++) {
            nums1[i] = nums[i];
            nums1[i + nums.length] = nums[i];
        }
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        for (int i = 0; i < nums1.length; i++) {
            for (int j = i + 1; j < nums1.length; j++) {
                if (nums1[j] > nums1[i]) {
                    res[i % nums.length] = nums1[j];
                    break;
                }
            }
        }
        return res;
    }
}
// 单调栈
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        // 构建递增的单调栈，存储数组索引，方便对当前索引右侧更大的一个值进行记录
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(res, -1);
        stack.add(0);
        // 遍历两倍数组大小，实现模拟循环的场景
        for (int i = 1; i < nums.length * 2; i++) {
            // 栈不为空且当前索引下数值大于栈顶索引数值
            while (!stack.isEmpty() && nums[i % nums.length] > nums[stack.peek()]) {
                res[stack.peek()] = nums[i % nums.length]; // 栈顶索引处的元素右侧存在更大的值为nums[i % nums.length]
                stack.pop(); // 栈顶索引弹出
            }
            stack.add(i % nums.length); // 否则将相应索引加入栈中
        } 
        return res;
    }
}

// 方法一：暴力
class Solution {
    public int trap(int[] height) {
        int ans = 0; // 存储可接到的雨水结果
        int n = height.length; 
        for (int i = 0; i < n; i++) {
            int leftMax = 0; // 当前位置左侧最大值
            int rightMax = 0; // 当前位置右侧最大值
            // 遍历找到左侧最高的柱子
            for (int j = i; j >= 0; i--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            // 遍历找到右侧最高的柱子
            for (int j = i; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            // 计算当前位置能接到的雨水量
            int minMax = Math.min(leftMax, rightMax);
            ans += minMax - height[i];
        }
        return ans;
    }
}
// 方法二：双指针
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] maxLeft = new int[len];
        int[] maxRight = new int[len];
        // 记录每个柱子左边柱子最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i < len; i++) {
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
        }
        // 记录每个柱子右边柱子最大高度
        maxRight[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            maxRight[i] = Math.max(maxRight[i + 1], height[i]);
        }
        // 求和
        int sum = 0;
        for (int i = 0; i < len; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
}
// 单调栈
class Solution {
    public int trap(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        for (int i = 1; i < height.length; i++) {
            if (height[i] < height[stack.peek()]) {
                stack.add(i);
            } else if (height[i] == height[stack.peek()]) {
                stack.pop();
                stack.add(i);
            } else {
                int nowHeight = height[i]; // 当前索引下的高度
                while (!stack.isEmpty() && (height[i] > height[stack.peek()])) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int left = stack.peek();
                        int h = Math.min(height[left], height[i]) - height[mid];
                        int w = i - left - 1;
                        int s = h * w;
                        if (s > 0) {
                            sum += s;
                        }
                    }
                }
                stack.add(i);
            }
        }
        return sum;
    }
}