题解 | #单调栈#

第一次遇到这种题，记录一下

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    //  严格的小于关系
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
      if (nums.empty()) {
        return std::vector<std::vector<int>>();
      }
      
      std::vector<std::vector<int>> res(nums.size(), std::vector<int>(2, -1));
      std::stack<int> single;
      res[0][0] = -1;
      single.push(0);
      
      //  找左边
      for (int i = 1; i < nums.size(); ++i) {
        while (!single.empty() && nums[i] <= nums[single.top()]) {
          single.pop();
        }
        if (single.empty()) {
          res[i][0] = -1;
        } else {
          res[i][0] = single.top();
        }
        single.push(i);
      }
      
      //  找右边
      res[nums.size() - 1][1] = -1;
      while (!single.empty()) {
        single.pop();
      }
      single.push(nums.size() - 1);
      
      for (int i = nums.size() - 2; i >= 0; --i) {
        while (!single.empty() && nums[i] <= nums[single.top()]) {
          single.pop();
        }
        if (single.empty()) {
          res[i][1] = -1;
        } else {
          res[i][1] = single.top();
        }
        single.push(i);
      }
      
      return res;
    }
};