向右看齐

---

单调栈

#include<bits/stdc++.h>
using namespace std;
int h[100001], ans[100001];
int main(){
  int n; scanf("%d",&n);  //奶牛数量
  for (int i=1;i<=n;i++)  scanf("%d",&h[i]);  //每头奶牛的高度
  stack<int>st; 
  for (int i=n;i>=1;i--){
    while (!st.empty() && h[st.top()] <= h[i])   
      st.pop();           //栈顶奶牛没i高，弹出它，直到栈顶奶牛更高为止
    if (st.empty())   ans[i]=0;              //栈空，没有仰望对象            
    else              ans[i]=st.top();       //栈顶奶牛更高，是仰望对象，不够高的弹出，留下仰望对象
    st.push(i);                              //进栈，每头牛都会记录下仰望对象
  }
  for (int i=1;i<=n;i++)   printf("%d\n",ans[i]);
  return 0;
}

笔记：入栈的牛要比栈顶的小，这样栈顶就是入栈牛的仰望对象，栈空仰望对象就是自己

手写栈

#include<bits/stdc++.h>
using namespace std;
const int N = 100100;
struct mystack{
    int a[N];                           //存放栈元素，int型
    int t = 0;                          //栈顶位置
    void push(int x){ a[++t] = x;  }    //送入栈
    int  top()      { return a[t]; }    //返回栈顶元素
    void pop()      { t--;         }    //弹出栈顶
    int empty()     { return t==0?1:0;} //返回1表示空
}st;
int h[N], ans[N];
int main(){
  int n;  scanf("%d",&n);
  for (int i=1;i<=n;i++)  scanf("%d",&h[i]);
  for (int i=n;i>=1;i--){
    while (!st.empty() && h[st.top()] <= h[i])   
      st.pop();                          //栈顶奶牛没i高，弹出它，直到栈顶奶牛更高            
    if (st.empty())   ans[i]=0;          //栈空，没有仰望对象
    else              ans[i]=st.top();   //栈顶奶牛更高，是仰望对象
    st.push(i);
  }
  for (int i=1;i<=n;i++)  printf("%d\n",ans[i]);
  return 0;
}

笔记：把上一个题解的STL stack 改成手写栈，保留栈的基本用法