广东省做农业网站销售的公司,一些难以发现的网站,正规的网店代运营,php商务网站开发单调栈
定义
单调栈是一种特殊的数据结构#xff0c;栈内元素保持某种单调性#xff08;通常是单调递增或单调递减#xff09;。
运用情况
求解下一个更大元素或下一个更小元素。计算每个元素左边或右边第一个比它大或小的元素。
注意事项
要明确单调栈是递增还是递减…单调栈
定义
单调栈是一种特殊的数据结构栈内元素保持某种单调性通常是单调递增或单调递减。
运用情况
求解下一个更大元素或下一个更小元素。计算每个元素左边或右边第一个比它大或小的元素。
注意事项
要明确单调栈是递增还是递减。注意处理边界情况。考虑时间复杂度单调栈的时间复杂度通常为 O(n)但在某些情况下可能需要进一步优化。
解题思路
以求解下一个更大元素为例
从左到右遍历数组。当栈为空或者当前元素大于等于栈顶元素时将当前元素入栈。当当前元素小于栈顶元素时栈顶元素出栈此时当前元素就是栈顶元素的下一个更大元素。
通过以上步骤可以在一次遍历中找到每个元素左侧第一个比它大的元素时间复杂度为 O(n)。
例如对于数组 [1, 3, 2, 4]使用单调递增栈来求解下一个更大元素
先将 1 入栈。3 大于 1将 1 出栈3 入栈此时 3 的下一个更大元素是无。2 小于 32 入栈。4 大于 2 和 32 出栈4 是 2 的下一个更大元素3 出栈4 是 3 的下一个更大元素然后 4 入栈。
处理栈为空的情况
直接返回如果在栈为空的情况下没有其他有效的操作或结果可以返回那么可以直接返回一个特定的值或标志表示栈为空的情况。初始化或重置有些情况下可以在栈为空时进行一些初始化或重置的操作例如将栈的一些属性设置为初始值或者将相关的数据结构进行初始化。抛出异常如果栈为空的情况被视为一种错误或异常情况可以抛出一个异常来通知调用者进行相应的处理。特殊逻辑处理根据具体的问题需求可以在栈为空时执行一些特殊的逻辑处理。这可能涉及到对问题的特殊判断或采取其他替代的计算方式。
例如在寻找左侧第一个比当前元素大的元素的问题中当栈为空时可以直接将当前元素入栈因为此时没有左侧更大的元素。
AcWing.830单调栈
题目描述
830. 单调栈 - AcWing题库 运行代码
#includeiostream
using namespace std;
const int N 1e5 10;
int main()
{int n,i,tt,stk[N],top-1;cin n;while (n--){int x;cinx;while(ttstk[tt]x){tt--;}if(tt) coutstk[tt] ;else cout-1 ;stk[tt]x;}
}
代码思路 初始化定义了变量n为序列长度i为循环变量未使用tt作为栈顶指针初始化为-1stk[]作为单调栈存储元素的下标top初始化为-1以标记栈为空。 输入与循环首先读取序列长度n然后进入循环每次循环读取一个元素x。 单调栈处理 使用while循环检查栈顶元素实际上为之前处理过的元素对应的下标是否大于等于当前元素x。如果是则这些元素不可能是后续元素的下一个更大元素因此从栈中弹出更新栈顶指针tt。弹出操作完成后如果栈非空即tt不为-1说明栈顶元素是当前x的下一个更大元素输出该元素的值注意代码直接输出了栈顶的值实际上是栈中元素对应的原序列值这里可能存在误导因为栈中存储的是下标。如果栈空说明当前元素右边没有更大的元素输出-1。最后将当前元素的下标入栈因为后续的元素可能以它为下一个更大元素。 循环直至所有元素处理完毕。
改进建议 变量命名变量命名可以更加明确例如将tt和top统一为更清晰的名称如stackTop将stk改为更具描述性的名称如indexStack并明确区分存储元素值和下标的栈。 输出逻辑调整代码直接从栈中输出元素值是不准确的应该存储元素值而不是下标并在需要时从原序列中提取元素值输出。或者在入栈时直接存储元素值并调整输出逻辑。 添加注释在关键操作前后添加注释解释每部分代码的功能提高代码可读性。 考虑边界情况虽然题目描述中可能默认输入合法但在实际编程中增加对输入数据合法性的检查是一个好习惯。 输出格式根据实际需求可能需要在所有元素处理完后输出一个换行符以符合常见输出格式。
