判断每个数右边有没有大于等于它的数,使用单调栈
时间复杂度$O(n)$
class Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
int n=heights.size();
vector<int>res(n);
stack<int>stk;
for(int i=n-1;i>=0;i--)
{
while(stk.size() && heights[stk.top()]<heights[i]) stk.pop();
if(stk.empty()) res[i]=n;
else res[i]=stk.top();
stk.push(i);
}
vector<int>ans;
for(int i=0;i<n;i++)
if(res[i]==n)
ans.push_back(i);
return ans;
}
};