【单调队列】154. 滑动窗口
时间: 2023-09-23 12:08:35 浏览: 52
单调队列是一种特殊的数据结构,用于解决滑动窗口问题。在滑动窗口问题中,要求在一个大小为k的窗口中,找到窗口内的最大值或最小值。单调队列通过维护一个单调递增或递减的队列,可以高效地解决这个问题。
具体实现上,可以使用两个单调队列,一个用于维护窗口内的最大值,另一个用于维护窗口内的最小值。在添加新元素时,如果队列不为空且要加入的元素值小于队列尾的值,则将队尾弹出,直到队尾小于要加入的元素或者队列为空。这样,队首就是当前窗口内的最大值或最小值了。
对于问题中提到的代码,首先定义了一个用于存储下标的队列stk,以及用于存储数组元素的数组a。然后通过一个循环,分别计算了窗口内的最小值和最大值。在计算最小值时,维护了一个单调递增的队列,即队首是窗口内的最小值。在计算最大值时,维护了一个单调递减的队列,即队首是窗口内的最大值。最后,输出计算结果。
总结起来,单调队列是一种解决滑动窗口问题的高效数据结构,可以通过维护单调递增或递减的队列来求解窗口内的最大值或最小值。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>
#### 引用[.reference_title]
- *1* [整数滑动窗口(acwing算法题C++)](https://blog.csdn.net/falldeep/article/details/118631830)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatgptT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [【Week5作业 D】滑动窗口【单调队列】](https://download.csdn.net/download/weixin_38647039/14916076)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatgptT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* *4* [【acwing】单调队列--154. 滑动窗口](https://blog.csdn.net/qq_43531919/article/details/115402227)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatgptT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]