TOJ 169

TOJ 169

題敘

https://toj.tfcis.org/oj/pro/169/
可見杆問題
給一群杆子的高度，求在每根杆子上向左看能看到的杆子數量總和
定義能看到是你所在的桿杆和該桿杆之間的所有桿杆高度都小於你所在的桿杆的高度

想法

觀察能被其他杆子看到的集合所形成的序列可以發現是呈現 遞增 的狀態
因此我們只要能維護一個嚴格遞增的序列，剩下的就必定會是能被看到的杆子
因為這裡的狀態是先進後出，跟stack一樣，所以選擇stack
stack的頂與當前元素之間的元素數量即為當前杆子能看到的數量

Code

//By Koios1143
#include<iostream>
#include<vector>
#define int long long
#define pii pair<int,int>
using namespace std;
const int Max_N = 1e7+10;
int t,n,m,arr[Max_N];
vector<int> st;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(cin>>t){
		st.clear();
		for(int i=1 ; i<=t ; i++){
			cin>>arr[i];
			while(!st.empty() && arr[i]>arr[st.back()])
				st.pop_back();
			if(i-1) cout<<' ';
			if(st.empty()) cout<<i-1;
			else cout<<(i-st.back()-1);
			st.push_back(i);
		}
		cout<<"\n";
	}
	return 0;
}

複雜度

掃過一次字串即可，複雜度 $O(t)$