题解 | JAVA #单调栈# [P0]

单调递增栈的解法这个讲的挺清楚的
就贴个java的code。

时间: O(n) 虽然是两层循环，但是每个数最多进/出栈一次
空间: O(n)

import java.util.*;

public class Solution {
    public int[][] foundMonotoneStack (int[] nums) {
      int[][] ans = new int[nums.length][2];
      // 找左边最近小数
      // stack规则: 从左向右push index，stack保持单调递增(相对于nums[index])
      Deque<Integer> stack = new ArrayDeque<>();
      for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] >= nums[i])
          stack.pop();
        // 此时stack的顶端一定是离nums[i]最近的左侧小数的下标
        ans[i][0] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
      }
      
      // 找右侧最近小数
      // stack规则: 从右向左push index，stack保持单调递增(相对于nums[index])
      stack.clear();
      for (int i = nums.length-1; i >=0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] >= nums[i])
          stack.pop();
        // 此时stack的顶端一定是离nums[i]最近的右侧小数的下标
        ans[i][1] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
      }
      
      return ans;
    }
}