題目描述

• 給定一個長度為N的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出?1。

輸入格式

• 第一行包含整數N，表示數列長度。
• 第二行包含N個整數，表示整數數列。

輸出格式

• 共一行，包含N個整數，其中第i個數表示第i個數的左邊第一個比它小的數，如果不存在則輸出?1。

數據范圍

• 1 ≤ N ≤ 10^5
• 1 ≤ 數列中元素 ≤ 109

基本思路

• 本題是單調棧最經典的應用情況。單調棧是指一個其中的元素是按照順序排列的棧。
• 基本思路為：
  • 首先構建一個空的整數類型的棧；
  • 每次讀取一個數組元素，進行判定：
    • 如果此時的棧為空，則直接輸出-1，然后將該元素入棧；
    • 如果此時的棧不為空，則將當前數組元素與棧頂元素比較。如果當前元素小于等于棧頂元素，則將棧頂元素出棧，然后比較當前元素和更新后的棧頂元素。重復上述過程，如果最終找到了一個比當前數組元素小的棧頂元素，則輸出該棧頂元素的值；如果沒有找到比當前數組小的棧頂元素（即把棧中的所有元素都出棧了，仍然沒有找到），則直接輸出-1 。最后，將當前的數組元素入棧。
  • 重復上述過程直到所有數組元素均輸入完成。

實現代碼

#include <cstdio>
#include <stack>
using namespace std;int main(void)
{int N;scanf("%d", &N);stack<int> sorted_stack;for(int i = 0; i < N; ++ i){int x;scanf("%d", &x);if(sorted_stack.empty()) printf("-1 ");else{while(!sorted_stack.empty() && sorted_stack.top() >= x) sorted_stack.pop();if(sorted_stack.empty()) printf("-1 ");else printf("%d ", sorted_stack.top());}sorted_stack.push(x);}return 0;
}