题解45-46 单调队列与单调栈

题解45:https://ac.nowcoder.com/acm/problem/50528 滑动窗口

这道题是求区间最大值,不是区间和最大值

属于单调队列的应用(模版题?)(与题解47单调队列区分)

AC代码&思路:

#include<iostream>
#include<deque>
using namespace std;
int a[1000010];
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  int n,k;cin>>n>>k;
  for(int i=1;i<=n;++i) {cin>>a[i];}
  deque<int> t1;
  for(int i=1;i<=n;++i)
  {
      while(!t1.empty() && a[t1.front()]>a[i]) {t1.pop_front();}
      t1.push_front(i);//退出循环的条件是队列空了或者a[i]>=t1,所以t1=>front,队首永远是当前最大值,往后一直递减
      if(t1.back()<=i-k) {t1.pop_back();}//即(i-队尾+1)>k移项得来//说明此时队尾已经超出滑动窗口的范围了,马上把它pop掉
      if(i>=k) {cout<<a[t1.back()]<<' ';}//在没有满第一个滑动窗口时,不输出.满了第一个滑动窗口后,一直都会满.由于单调队列是递减的,队尾最小
  }
  cout<<'\n';
  t1.clear();//清空
//下面求最大值,分析同上
  for(int i=1;i<=n;++i)
  {
      while(!t1.empty() && a[t1.front()]<a[i]) {t1.pop_front();}
      t1.push_front(i);
      if(t1.back()<=i-k) {t1.pop_back();}
      if(i>=k) {cout<<a[t1.back()]<<' ';}
  }
  return 0;
}

题解46:https://ac.nowcoder.com/acm/problem/24840 Look Up

农民约翰的 N （1 <= N <= 100,000） 奶牛，方便编号为 1..N，再次排成一排。牛 i 的身高为 Hi （1 <= Hi <= 1,000,000）。 每头奶牛都向左看那些索引数较高的奶牛。我们说，如果我< j 和 Hi < Hj，我们说母牛 i “仰望”母牛 j。对于每头奶牛 i，FJ 想知道奶牛 i 所仰望的第一头奶牛的指数。

是题解45单调队列的同类题(单调栈),也是题解47的前身

因为这道题不用操作队尾,所以用栈作为数据结构就够了

AC代码&思路:

#include<iostream>
#include<stack>
using namespace std;
int a[100010];
int res[100010];
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  int n;cin>>n;
  for(int i=1;i<=n;++i) {cin>>a[i];}
  stack<int> st;
  for(int i=n;i>=1;--i)//从右向左检索,遇到最高的就会把更右边的挡住,遇到更矮的还有可能在左边更矮的以它为榜样
  {
      while(!st.empty() && a[st.top()]<=a[i]) {st.pop();}
    //比a[i]小的扔掉,因为左边没人再拿它们当榜样,循环退出时如果st非空,那么他一定大于a[i],且离a[i]最近,a[i]可以拿它当榜样
      if(!st.empty()) {res[i]=st.top();}//默认初始化为0
      st.push(i);//因为最后要求输出数组下标而不是元素值,所以这里就将数组下标存入
  }
  for(int i=1;i<=n;++i) {cout<<res[i]<<'\n';}
  return 0;
}