題目背景
模闆題，無背景。
2019.12.12 更新資料，放寬時限，現在不再卡常了。
題目描述
給出項數為 nn 的整數數列 a_{1 \dots n}a1…n。
定義函數 f(i)f(i) 代表數列中第 ii 個元素之後第一個大于 a_iai 的元素的下标，即 f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}f(i)=mini<j≤n,aj>ai{j}。若不存在，則 f(i)=0f(i)=0。
試求出 f(1\dots n)f(1…n)。
輸入格式
第一行一個正整數 nn。
第二行 nn 個正整數 a_{1\dots n}a1…n。
輸出格式
一行 nn 個整數 f(1\dots n)f(1…n) 的值。
輸入輸出樣例
輸入 #1複制
5
1 4 2 3 5
輸出 #1複制
2 5 4 5 0
概念：單調遞增或單調減的棧，跟單調隊列差不多，但是隻用到它的一端
題意分析：給一個數字n代表輸入n個數；第二行輸入這n個數
結果輸出每個數右邊第一個比它大的數；若無輸出0
1，雙for曆遍
對每一個曆遍元素，運用一個for循環，去查找它右邊第一個大于它的數
2，單調棧（重點講）
以樣本資料為例子：
5
1 4 2 3 5
 |
| |
| 滿足條件2 |
| |
| 滿足條件1 |
| |
| |
| |
| 滿足條件1 |
| |
| |
| 滿足條件2 |
| |
| 滿足條件1 |
| |
| |
| 滿足條件2 |
| |
| |
| 滿足條件2 |
這就是單調棧運作的具體流程圖 在本題中，我們在維護單調棧的同時，也需要記錄其結果的對應下标 于是，我們需要 建立相關的數組來記錄相應的資料
1,資料數組：記錄輸入的n個數 dataArrary[]
2.下标數組：記錄曆遍元素的下标 cursorArray[]
3.結果數組：記錄最終的答案 answerArray[]
另需一個top值，來表示目前棧中的元素數量
條件1：若此時棧為空或曆遍元素小于等于棧頂元素，把其加入棧中（壓棧）
條件2：若此時曆遍元素大于棧頂元素，彈出棧頂元素，循環，直至不滿足條件2或棧為空
轉換為對應的代碼為：
for (int i = 1; i < data.length; i++) {
//滿足條件二
while (top != 0 && data[i] > data[cursor[top]]) {
answer[cursor[top]] = i;
stack.pop();
top--;
}
//滿足條件一
stack.push(data[i]);
top++;
cursor[top] = i;
}
資料轉換過程：
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,0,0,0,0,0] answerArray=[0,0,0,0,0,0] Top=0 i=1 data[1]=1 |
| 滿足條件一 cursor[top]=i Top++; Top=1 cursorArray=[0,1,0,0,0,0] answerArray=[0,0,0,0,0,0] |
| |
| |
| |
| dataArray=[0,1,4,2,3,5] Top=1 i=2 data[i]=4 |
| While(滿足條件二) Answer[cursor[top]]=i Top--; Top=0; cursorArray=[0,1,0,0,0,0] answerArray=[0,2,0,0,0,0] |
| |
| Top=0 滿足條件一： cursor[top]=i Top++ Top=1 cursorArray=[0,2,0,0,0,0] answerArray=[0,2,0,0,0,0] |
| |
| |
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,2,0,0,0,0] answerArray=[0,2,0,0,0,0] Top=1 i=3 data[i]=2 滿足條件一： Top++ cursor[top]=i Top=2 cursorArray=[0,2,3,0,0,0] answerArray=[0,2,0,0,0,0] |
| |
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,2,3,0,0,0] answerArray=[0,2,0,0,0,0] Top=2 i=4 dataArray[i]=3 While(滿足條件2): Answer[curosr[top]]=i Top--; Top=1; cursorArray=[0,2,3,0,0,0] answerArray=[0,2,0,4,0,0] |
| |
| 滿足條件1 Top++; Cursor[top]=i Top=2 cursorArray=[0,2,4,0,0,0] answerArray=[0,2,0,4,0,0] |
| |
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,2,4,0,0,0] answerArray=[0,2,0,4,0,0] Top=2 i=5 dataArray[i]=5 While(滿足條件2): answer[cursor[top]]=i Top-- Top=0; cursorArray=[0,2,4,0,0,0] answerArray=[0,2,5,4,5,0] |
| |
| |
放下源碼：
import java.io.*;
import java.util.Stack;
public class 單調棧 {
public static void main(String[] args) throws IOException {
StreamTokenizer r = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
Stack stack = new Stack();
r.nextToken();
int n = (int) r.nval;
int data[] = new int[n + 1];
int cursor[] = new int[n + 1];
int answer[] = new int[n + 1];
int top = 0;
//輸入資料
for (int i = 1; i < data.length; i++) {
r.nextToken();
data[i] = (int) r.nval;
}
//維護單調棧
for (int i = 1; i < data.length; i++) {
//滿足條件二
while (top != 0 && data[i] > data[cursor[top]]) {
answer[cursor[top]] = i;
stack.pop();
top--;
}
//滿足條件一
stack.push(data[i]);
top++;
cursor[top] = i;
}
//輸出結果
for (int i = 1; i < answer.length; i++) {
if (i != answer.length - 1) {
pr.print(answer[i] + " ");
pr.flush();
} else {
pr.print(answer[i]);
pr.flush();
}
}
}
}
順便附贈一個C++代碼：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
int data[maxn], cursor[maxn], answe[maxn], top = 0; //top==0表示空棧
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &data[i]);
//從棧底到棧頂的下标對應的數組值(優先級)依次遞減
for (int i = 1; i <= n; ++i) {
//将先進棧(前面的元素下标)且<arr[i]的值的坐标清除掉
//并記錄data[i]的下标作為前面的答案
while (top && data[cursor[top]] < order[i]) answer[cursor[top--]] = i;
curso[++top] = i; //存儲arr的數組下标
}
for (int i = 1; i <= n; ++i) {
if (i == 1) printf("%d", answer[i]);
else printf(" %d", answer[i]);
}
return 0;
}