微信公众号商城网站开发网站建设适用税种

微信公众号商城网站开发,网站建设适用税种,百度营消 营销推广,深圳全网推广托管对前端开发者而言#xff0c;学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始#xff0c;每天投入一小段时间#xff0c;结合前端场景去理解和练习…对前端开发者而言学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始每天投入一小段时间结合前端场景去理解和练习你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法资深前端开发者的进阶引擎LeetCode 155. 最小栈1. 题目描述1.1 原题链接与基本信息题目链接LeetCode 155. 最小栈难度简单标签栈、设计1.2 题目描述与示例设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现MinStack类:MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。示例 1:输入 [MinStack,push,push,push,getMin,pop,top,getMin] [[],[-2],[0],[-3],[],[],[],[]] 输出 [null,null,null,null,-3,null,0,-2] 解释 MinStack minStack new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); -- 返回 -3. minStack.pop(); minStack.top(); -- 返回 0. minStack.getMin(); -- 返回 -2.提示-2^31 val 2^31 - 1pop、top和getMin操作总是在非空栈上调用。最多调用3 * 10^4次push、pop、top和getMin。2. 问题分析2.1 问题核心我们需要实现一个特殊的栈它除了支持常规的栈操作push、pop、top外还需要支持在常数时间内返回当前栈中的最小元素。2.2 难点分析常规的栈结构可以在常数时间内完成push、pop、top操作但是要获取最小值通常需要遍历整个栈时间复杂度为 O(n)不符合题目要求。因此我们需要在数据结构和算法上进行设计使得getMin操作的时间复杂度为 O(1)。3. 解题思路3.1 思路一辅助栈法最优解使用两个栈一个主栈用于存储所有元素另一个辅助栈用于存储主栈每个状态下的最小值。当元素入栈时主栈正常压入辅助栈则压入当前主栈的最小值即辅助栈栈顶和当前值中的较小者。出栈时两个栈同时弹出栈顶元素。这样辅助栈的栈顶始终对应主栈当前状态的最小值。3.2 思路二单个栈存储差值法只使用一个栈存储每个元素与当前最小值的差值。同时用一个变量min记录当前最小值。入栈时压入差值并更新最小值出栈时根据栈顶差值反向更新最小值。这种方法节省了空间但实现稍复杂且需要注意整数溢出问题JavaScript 使用 Number 类型安全整数范围为-2^53 ~ 2^53题目值范围在 32 位整数内因此安全。3.3 思路三节点存储当前最小值法定义一个节点结构每个节点存储当前值以及到该节点为止的最小值。这样栈中每个元素都携带了当前状态的最小值信息。出栈操作不影响其他节点的最小值。这种方法同样可以实现常数时间获取最小值但每个节点需要额外存储一个最小值空间复杂度为 O(n)。4. 代码实现4.1 辅助栈法JavaScript实现classMinStack{constructor(){this.stack[];this.minStack[];// 辅助栈与主栈同步操作栈顶存储当前主栈中的最小值}push(val){this.stack.push(val);// 如果辅助栈为空或者当前值小于等于辅助栈栈顶则压入当前值否则重复压入辅助栈栈顶if(this.minStack.length0||valthis.minStack[this.minStack.length-1]){this.minStack.push(val);}else{this.minStack.push(this.minStack[this.minStack.length-1]);}}pop(){if(this.stack.length0)return;this.stack.pop();this.minStack.pop();}top(){returnthis.stack[this.stack.length-1];}getMin(){returnthis.minStack[this.minStack.length-1];}}4.2 差值法JavaScript实现classMinStack{constructor(){this.stack[];this.minInfinity;// 当前最小值}push(val){if(this.stack.length0){this.stack.push(0);// 差值为0this.minval;}else{constdiffval-this.min;this.stack.push(diff);// 如果差值小于0说明val比当前最小值还小更新最小值if(diff0){this.minval;}}}pop(){if(this.stack.length0)return;constdiffthis.stack.pop();// 如果差值小于0说明当前栈顶元素就是最小值出栈后需要恢复前一个最小值if(diff0){this.minthis.min-diff;// 因为 diff val - oldMin, 且 val 就是当前的 min所以 oldMin min - diff}// 如果栈为空重置minif(this.stack.length0){this.minInfinity;}}top(){constdiffthis.stack[this.stack.length-1];// 如果差值大于等于0说明当前栈顶元素不是最小值真实值为 min diff// 如果差值小于0说明当前栈顶元素是最小值真实值就是 minreturndiff0?this.mindiff:this.min;}getMin(){returnthis.min;}}4.3 节点存储法JavaScript实现classMinStack{constructor(){this.stack[];// 栈中每个元素是一个对象包含val和当前最小值}push(val){if(this.stack.length0){this.stack.push({val,min:val});}else{constcurrentMinthis.stack[this.stack.length-1].min;this.stack.push({val,min:Math.min(currentMin,val)});}}pop(){this.stack.pop();}top(){returnthis.stack[this.stack.length-1].val;}getMin(){returnthis.stack[this.stack.length-1].min;}}5. 复杂度与优缺点对比5.1 复杂度分析方法时间复杂度 (push/pop/top/getMin)空间复杂度辅助栈法O(1)O(n)差值法O(1)O(n) (最坏情况下与辅助栈法相同但平均情况下节省空间)节点存储法O(1)O(n)5.2 优缺点对比表格方法优点缺点辅助栈法思路直观易于理解和实现操作同步逻辑简单。需要额外的栈最坏情况下空间加倍。差值法只使用一个栈节省了空间尤其当元素较多且最小值变化不大时。实现稍复杂需要考虑整数溢出在JavaScript中问题不大存储差值可能带来精度问题但题目为整数所以安全。节点存储法每个节点独立存储最小值逻辑清晰不需要额外数据结构。每个节点需要额外存储一个最小值空间开销与辅助栈法类似。最优解建议辅助栈法。因其实现简单可读性强在大多数情况下是首选。虽然空间复杂度为 O(n)但实际应用中通常可以接受。6. 总结最小栈问题是一个经典的栈结构设计问题其核心在于如何在维护栈的先进后出特性的同时快速获取当前状态下的最小值。通过辅助栈、差值法或节点存储法我们都可以在 O(1) 时间复杂度内完成所有操作。其中辅助栈法是最直接和常用的方法适合在面试和实际开发中快速实现。