考试时间：14：30 - 16：00

解题策略

• T1： 栈

void solve(int arr[], int n){
	
	stack<int>st; //保存下标索引 
	st.push(1);
	for(int i = 2; i <= n; i ++){
		while(!st.empty()&& arr[st.top()] < arr[i]){ // 栈内元素数量不为空 且 栈顶元素小于即将放入的元素 
			f[st.top()] = i;  // 将栈顶的索引位置的值设置为 i 
			st.pop()
		}  
		st.push(i);
	}
	while(!st.empty()){
		f[st.top()] = 0;
		st.pop();
	}
}

• T2：贪心

int solve2(int arr[], int n){
	int ans = 0;
	for(int i = 1; i <= n; i ++){
		if(arr[i] > arr[i-1]){
			ans += (arr[i] - arr[i-1]);
		}
	}
	return ans;
} 

• T3：二分+单调队列

int que[N];
int head = 0;
int tail = -1;
int f[N]; // 以 i 道题 为结尾 所耗费的时间 
int time[N];
bool check(int mid){
	
	for(int i = 1; i <= n; i ++){
		// step1；队尾出队
		while(tail >= head && time[que[tail]] >= time[i]) tail --;
		// step2: 队尾入队
		que[tail++] = i; 
		
		// step3: 队首出队
		if(i - que[head] > mid) head ++;
		
		if(i > mid){
			f[i] = time[i] + time[que[head]];
		}else{
			f[i] = time[que[head]];
		}
	 	
	 	if(f[i] > Time) return false;
	}
	return true;
}
// 二分答案 
int biSearch(int l, int r){
	while((l + 1) < r){
		int mid = (l + r) >> 1;
	    if(check(mid) == true){
	    	l = mid;
		}else{
			r = mid;
		}
	}
	return l;
}