package jjn.carl.monotonic_stack;
import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.Scanner;
/** * @author Jiang Jining * @since 2023-08-27 9:21 */public class LeetCode503 {    public int[] nextGreaterElements(int[] nums) {        if (nums.length <= 1) {            return new int[]{-1};        }        Deque<Integer> deque = new ArrayDeque<>();        int[] next = new int[nums.length];        Arrays.fill(next, -1);        for (int i = 0; i < nums.length * 2; i++) {            while (!deque.isEmpty() && nums[i % nums.length] > nums[deque.peekLast()]) {                next[deque.peekLast()] = nums[i % nums.length] ;                deque.pollLast();            }            deque.offer(i % nums.length);        }        return next;    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int total = scanner.nextInt();        int[] nums = new int[total];        for (int i = 0; i < total; i++) {            nums[i] = scanner.nextInt();        }        int[] nextGreaterElements = new LeetCode503().nextGreaterElements(nums);        System.out.println(Arrays.toString(nextGreaterElements));    }}

package jjn.carl.monotonic_stack;
import java.util.Scanner;import java.util.Stack;
/** * @author Jiang Jining * @since 2023-08-27 10:06 */public class LeetCode42 {    public int trap(int[] height) {        int length = height.length;        if (length <= 2) return 0;        int[] maxLeft = new int[length];        int[] maxRight = new int[length];                // 记录每个柱子左边柱子最大高度        maxLeft[0] = height[0];        for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);                // 记录每个柱子右边柱子最大高度        maxRight[length - 1] = height[length - 1];        for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);                // 求和        int sum = 0;        for (int i = 0; i < length; i++) {            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];            if (count > 0) sum += count;        }        return sum;    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int total = scanner.nextInt();        int[] height = new int[total];        for (int i = 0; i < total; i++) {            height[i] = scanner.nextInt();        }        int trap = new LeetCode42().trap(height);        System.out.println(trap);    }}