单调栈和单调队列()

P5788 【模板】单调栈

入栈时候判定,如果不符合栈内的规则,则让栈顶的元素出栈。

入栈时候判定,如果不符合栈内的规则,则让栈顶的元素出栈。

void solve() {
  stack<int> sc;
  ufr(i, 1, n) {
    if (sc.empty()) {
      sc.emplace(i);
      continue;
    }
    while (!sc.empty() && nums[sc.top()] < nums[i]) {
      ans[sc.top()] = i;
      sc.pop();
    }
    sc.emplace(i);
  }
}

P1886 单调队列

使用双端队列进行实现,\(STL\)库\(deque\)

使用双端队列进行实现,\(STL\)库\(deque\)

  • 单调队列中存储的是下标,而不是元素的值
  • 让即将入队的元素,与队列末尾元素对应其数组中的值比较,如果不符合队列规则,便出队。
  • 模拟滑动窗口,则让即将入队的下标,与队首元素做差值,如果大于窗口长度则让队首元素出队,因为队首元素是最先放入队列的元素。
  • 求某个移动范围的动态最值,如果队列保持一定的规则,那么队首元素对应数组中的值,是队列中的最值

规则:该队列是单调递减还是递增?

规则:该队列是单调递减还是递增?

递增单调队列

  deque<int> que;
  ufr(i, 1, n) {
    if (!que.empty() && i - que.front() >= k) que.pop_front();
    while (!que.empty() && nums[que.back()] >= nums[i]) que.pop_back();
    que.emplace_back(i);
    if (i >= k) f.pt(nums[que.front()]).ptc(' ');
  }

递减单调队列

  ufr(i, 1, n) {
    if (!que.empty() && i - que.front() >= k) que.pop_front();
    while (!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
    que.emplace_back(i);
    if (i >= k) f.pt(nums[que.front()]).ptc(' ');
  }

单调队列优化多重背包

————————

P5788 【模板】单调栈

入栈时候判定,如果不符合栈内的规则,则让栈顶的元素出栈。

入栈时候判定,如果不符合栈内的规则,则让栈顶的元素出栈。

void solve() {
  stack<int> sc;
  ufr(i, 1, n) {
    if (sc.empty()) {
      sc.emplace(i);
      continue;
    }
    while (!sc.empty() && nums[sc.top()] < nums[i]) {
      ans[sc.top()] = i;
      sc.pop();
    }
    sc.emplace(i);
  }
}

P1886 单调队列

使用双端队列进行实现,\(STL\)库\(deque\)

使用双端队列进行实现,\(STL\)库\(deque\)

  • 单调队列中存储的是下标,而不是元素的值
  • 让即将入队的元素,与队列末尾元素对应其数组中的值比较,如果不符合队列规则,便出队。
  • 模拟滑动窗口,则让即将入队的下标,与队首元素做差值,如果大于窗口长度则让队首元素出队,因为队首元素是最先放入队列的元素。
  • 求某个移动范围的动态最值,如果队列保持一定的规则,那么队首元素对应数组中的值,是队列中的最值

规则:该队列是单调递减还是递增?

规则:该队列是单调递减还是递增?

递增单调队列

  deque<int> que;
  ufr(i, 1, n) {
    if (!que.empty() && i - que.front() >= k) que.pop_front();
    while (!que.empty() && nums[que.back()] >= nums[i]) que.pop_back();
    que.emplace_back(i);
    if (i >= k) f.pt(nums[que.front()]).ptc(' ');
  }

递减单调队列

  ufr(i, 1, n) {
    if (!que.empty() && i - que.front() >= k) que.pop_front();
    while (!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
    que.emplace_back(i);
    if (i >= k) f.pt(nums[que.front()]).ptc(' ');
  }

单调队列优化多重背包