题意:n个房子高度为hi,i满足以下任一条件可以跳到j
- ?+1=?
- max(??+1,…,???1)<min(??,??)
- max(??,??)<min(??+1,…,???1)
用一个递增和一个递减的单调栈分别记录第三种转移和第二种转移
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 50;
int main()
{int n;while(cin>>n){stack<int> q1, q2;vector<int>h(n + 1),dp(n+1);for(int i = 1; i <= n; ++i)cin>>h[i];dp[1] = 0;q1.push(1),q2.push(1);for(int i=2;i<=n;++i){dp[i]=dp[i-1]+1;while(!q1.empty()&&h[q1.top()] <= h[i]){int t = q1.top();q1.pop();if(h[i] > h[t] && !q1.empty())dp[i] = min(dp[i], dp[q1.top()] + 1);}q1.push(i);while (!q2.empty() && h[q2.top()] >= h[i]) {int t = q2.top();q2.pop();if(h[i] < h[t] && !q2.empty())dp[i] = min(dp[i], dp[q2.top()] + 1);}q2.push(i);}cout << dp[n] << endl;}
}