题解 | 单调栈

import java.util.*;

/**
 * NC157 单调栈
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        int n = nums.length;
        int[][] results = new int[n][2];

        // 从左往右 遍历
        Stack<Integer> leftStack = new Stack<>();
        // 从右往左 遍历
        Stack<Integer> rightStack = new Stack<>();

        for(int i=0; i<n; i++){
            // 左边最近位置l -> 单调栈 单调增(从左往右)
            while(!leftStack.isEmpty() && nums[leftStack.peek()]>=nums[i]){
                leftStack.pop();
            }
            if(leftStack.isEmpty()){
                results[i][0] = -1;
            }else{
                results[i][0] = leftStack.peek();
            }
            leftStack.push(i);

            // 右边最近位置r -> 单调栈 单调增(从右往左)
            while(!rightStack.isEmpty() && nums[rightStack.peek()]>=nums[n-1-i]){
                rightStack.pop();
            }
            if(rightStack.isEmpty()){
                results[n-1-i][1] = -1;
            }else{
                results[n-1-i][1] = rightStack.peek();
            }
            rightStack.push(n-1-i);
        }

        return results;
    }
}