单调栈 | 个人笔记

单调递增，从栈顶到栈底依次递增

 1public static void sortStackIncrease() {
 2    int[] data = {2, 7, 5, 4, 6, 3, 4, 2};
 3    Stack<Integer> stack = new Stack<>();
 4    for (Integer val : data) {
 5        while (!stack.isEmpty() && stack.peek() <= val) {
 6            stack.pop();
 7        }
 8        stack.push(val);
 9    }
10    System.out.println(stack);
11}

单调递减，从栈顶到栈底依次递减

 1public static void sortStackDecrease() {
 2    int[] data = {4, 3, 2, 5, 7, 4, 6, 8};
 3    Stack<Integer> stack = new Stack<>();
 4    for (Integer val : data) {
 5        while (!stack.isEmpty() && stack.peek() >= val) {
 6            stack.pop();
 7        }
 8        stack.push(val);
 9    }
10    System.out.println(stack);
11}

找到数组右边第一个比它大的元素，第1种实现，基于倒序号，自己有些看不懂

 1public static void nextGreaterElement() {
 2    int[] data = {2, 7, 5, 4, 6, 3, 4, 2};
 3    int[] result = new int[data.length];
 4    Stack<Integer> stack = new Stack<>();
 5    // 单调递增
 6    for (int i = data.length - 1; i >= 0; i--) {
 7        int val = data[i];
 8        while (!stack.isEmpty() && stack.peek() <= val) {
 9            stack.pop();
10        }
11        result[i] = stack.empty() ? -1 : stack.peek();
12        stack.push(val);
13    }
14    System.out.println(stack);
15    System.out.println(StringUtils.join(ArrayUtils.toObject(result), ","));
16}

符合常规思维的从左到右的实现，此时记录的是下标值

 1public static void nextGreaterElement() {
 2    int[] data = {2, 7, 5, 4, 6, 3, 4, 2};
 3    int[] result = new int[data.length];
 4    Arrays.fill(result, -1);
 5    Stack<Integer> stack = new Stack<>();
 6    // 单调递增
 7    for (int i = 0; i < data.length; i++) {
 8        int val = data[i];
 9        while (!stack.isEmpty() && data[stack.peek()] < val) {
10            result[stack.pop()] = val;
11        }
12        stack.push(i);
13    }
14    System.out.println(stack);
15    System.out.println(StringUtils.join(ArrayUtils.toObject(result), ","));
16}