搜索

单调栈和单调队列


发布时间: 2022-11-25 00:37:00    浏览次数:35 次

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\)

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

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

递增单调队列

  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(' ');
  }

单调队列优化多重背包

免责声明 单调栈和单调队列,资源类别:文本, 浏览次数:35 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-25 12:37:00。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/GuanStudy/p/16923954.html