题解 | #单源最短路#

单调栈，ps单调栈用的最多的就是贪心+单调栈了吧

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        vector<vector<int>> ans(nums.size(), vector<int>(2, -1));
        vector<int> stk1, stk2;

        for (int i = 0; i < nums.size(); i++) {
            while (!stk1.empty() && nums[i] < nums[stk1.back()]) {
                ans[stk1.back()][1] = i;
                stk1.pop_back();
            }
            stk1.push_back(i);
            while (!stk2.empty() && nums[nums.size() - i - 1] < nums[stk2.back()]) {
                ans[stk2.back()][0] = nums.size() - i - 1;
                stk2.pop_back();
            }
            stk2.push_back(nums.size() - i - 1);
        }
        return ans;
    }
};