程序员代码面试指南 1.8：单调栈结构

1、思路

• 维护一个单调栈来寻找数组中每个元素左右两个方向上离它最近且比它小的元素；
• 遍历数组，让数组元素的下标进栈，栈中元素所代表的的值从下往上是单调递增的；
• 若当前元素小于栈顶元素，说明找到了栈顶元素右边第一个小于它且离它最近的数，且该栈顶元素左边第一个小于它且离它最近的数就是栈顶的后一个元素；
• 遍历完数组后，栈中元素依然单调递增，注意此时栈中所有元素的右边都没有小于它的元素了，依次出栈即可；
• 注意每一个出栈的元素，其左右位置都已经标记好了。所以每个元素只需要进栈出栈各一次，时间复杂度与空间复杂度都为。

2、代码

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<pair<int, int>> getNearLessPosition(vector<int>& nums)
{
    vector<pair<int, int>> res(nums.size());
    stack<int> stk;

    for (int i = 0; i < nums.size(); ++ i)
    {
        while (!stk.empty() && nums[stk.top()] > nums[i])
        {
            int popIndex = stk.top();
            stk.pop();
            int leftLessIndex = stk.empty() ? -1 : stk.top();
            res[popIndex].first = leftLessIndex;            //当前数左边第一个比它小的数
            res[popIndex].second = i;                       //i所代表的数是当前这个数右边第一个比它小的数
        }                                                   //注意每一个出栈元素，它的左右位置都已经标记好了
        stk.push(i);
    }

    while (!stk.empty())
    {
        int popIndex = stk.top();
        stk.pop();
        int leftLessIndex = stk.empty() ? -1 : stk.top();
        res[popIndex].first = leftLessIndex;
        res[popIndex].second = -1;                            //因为是单调栈，右边已经没有比它更小的数了
    }

    return res;
}

int main()
{
    int n;
    cin >> n;

    vector<int> nums;
    while (n -- )
    {
        int tmp;
        cin >> tmp;
        nums.push_back(tmp);
    }

    auto res = getNearLessPosition(nums);

    for (auto& i : res)
    {
        cout << i.first << " " << i.second << endl;
    }

    return 0;
}