leetcode：单调栈结构(进阶)

题目来源

• 牛客网

题目描述

题目解析

#include <vector>
#include <iostream>
std::vector<int> arr(1000000);
std::vector<std::vector<int>> ans(1000000, std::vector<int>(2));
// stack1 : 相等值的位置也放
// stack2 : 只放不相等值的最后一个位置
// 比如 : arr = { 3, 3, 3, 4, 4, 6, 6, 6}
// 位置 0 1 2 3 4 5 6 7
// 如果位置依次压栈，
// stack1中的记录是（位置） : 0 1 2 3 4 5 6 7
// stack1中的记录是（位置） : 2 4 7
std::vector<int> stack1(1000000);
std::vector<int> stack2(1000000);
void getNearLess(int n){
    
    int stackSize1 = 0;
    int stackSize2 = 0;

    for (int i = 0; i < n; ++i) {
    
        while (stackSize1 > 0 && arr[stack1[stackSize1 - 1]] > arr[i]) {
    
            int curIndex = stack1[--stackSize1];
            int left = stackSize2 < 2 ? -1 : stack2[stackSize2 - 2];
            ans[curIndex][0] = left;
            ans[curIndex][1] = i;
            if (stackSize1 == 0 || arr[stack1[stackSize1 - 1]] != arr[curIndex]) {
    
                stackSize2--;
            }
        }
        if (stackSize1 != 0 && arr[stack1[stackSize1 - 1]] == arr[i]) {
    
            stack2[stackSize2 - 1] = i;
        } else {
    
            stack2[stackSize2++] = i;
        }
        stack1[stackSize1++] = i;
    }

    while (stackSize1 != 0) {
    
        int curIndex = stack1[--stackSize1];
        int left = stackSize2 < 2 ? -1 : stack2[stackSize2 - 2];
        ans[curIndex][0] = left;
        ans[curIndex][1] = -1;
        if (stackSize1 == 0 || arr[stack1[stackSize1 - 1]] != arr[curIndex]) {
    
            stackSize2--;
        }
    }
}

int main()
{
    
    int n ;
    std::cin >> n;
    
    for (int i = 0; i < n; ++i) {
    
        std::cin >> arr[i];
    }

    getNearLess(n);
    
    std::string builder;
    for (int i = 0; i < n; ++i) {
    
       builder = builder + std::to_string(ans[i][0]) + " " +  std::to_string(ans[i][1]) + "\n";
    }
    
    std::cout << builder << "\n";
    return 0;
}