经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
LeetCode155:最小栈,最简单的中等难度题,时间击败100%,内存也低于官方
来源:cnblogs  作者:程序员欣宸  时间:2023/9/11 6:42:24  对本文有异议

欢迎访问我的GitHub

这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos

本篇概览

  • 最近运气不错,在LeetCode上白捡一道送分题,官方设定的难度是中等,然而此题难度放在简单的题库中都是垫底的存在,对于刷题数太少的欣宸而言,这简直就是力扣的馈赠,建议大家也不要错过,花上几分钟将其拿下
  • 不唠嗑了,下面咱们一起来刷之
  • 为了提起您的兴趣,这里提前剧透一下:
  1. 用最简单的数据结构-数组,来存储数据,代码整体非常简单,适合新手阅读
  2. 执行用时执行用时3毫秒, 在所有 Java 提交中击败了100%的用户(包括官方),有下图为证
    在这里插入图片描述

题目说明

  • 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
  • 实现 MinStack 类:
  1. MinStack() 初始化堆栈对象。
  2. void push(int val) 将元素val推入堆栈。
  3. void pop() 删除堆栈顶部的元素。
  4. int top() 获取堆栈顶部的元素。
  5. int getMin() 获取堆栈中的最小元素。
  • 示例1
  1. 输入:
  2. ["MinStack","push","push","push","getMin","pop","top","getMin"]
  3. [[],[-2],[0],[-3],[],[],[],[]]
  4. 输出:
  5. [null,null,null,null,-3,null,0,-2]
  6. 解释:
  7. MinStack minStack = new MinStack();
  8. minStack.push(-2);
  9. minStack.push(0);
  10. minStack.push(-3);
  11. minStack.getMin(); --> 返回 -3.
  12. minStack.pop();
  13. minStack.top(); --> 返回 0.
  14. minStack.getMin(); --> 返回 -2.
  • 提示
  1. -231 <= val <= 231 - 1
  2. pop、top 和 getMin 操作总是在 非空栈 上调用
  3. push, pop, top, and getMin最多被调用 30000 次

官方解法

  • 先来看官方解法,简单的说,就是用JDK已有的栈对象Deque来完成push、pop、top等操作,如下所示
  1. class MinStack {
  2. Deque<Integer> xStack;
  3. Deque<Integer> minStack;
  4. public MinStack() {
  5. xStack = new LinkedList<Integer>();
  6. minStack = new LinkedList<Integer>();
  7. minStack.push(Integer.MAX_VALUE);
  8. }
  9. public void push(int x) {
  10. xStack.push(x);
  11. minStack.push(Math.min(minStack.peek(), x));
  12. }
  13. public void pop() {
  14. xStack.pop();
  15. minStack.pop();
  16. }
  17. public int top() {
  18. return xStack.peek();
  19. }
  20. public int getMin() {
  21. return minStack.peek();
  22. }
  23. }
  • 读完这段代码我就茫然了:我来LeetCode刷题是为了什么?为了学习Deque类的API使用方法吗?
  • 不,我是来学习和提升自己的算法能力的,这种API调用并不是我心目中的答案,官方找不到,我就自己动手
  • 毕竟,实现个栈能有多大难度?
  • 为了弄清楚自己和官方的差距,我先将上述官方源码提交一次,看看成绩如何,如下图,官方在使用Deque类的情况下,执行用时击败93%,内存消耗击败57%
    在这里插入图片描述
  • 接下来该我了,自己实现栈

题目分析

  • 前面废话太多,这里精简一下,说说我理解的此题的重点
  1. 数据结构:怎么存数据,才能保证高效的读写速度?
  2. 最小值问题:本题不仅要有基本的栈功能,还要时刻能返回栈内的最小值
  3. 内存怎么优化?
  4. 耗时怎么优化?
  • 接下来针对上述问题,逐个考虑

问题一:数据结构设计

  • 最高效的存取,一般是数组和链表,在java中,原始类型的数组更简单,而链表就要用到对象了,相对更复杂,所以,数组是首选,至于用数组实现后进先出的栈,那也简单嘛,用个int型变量做指针即可
  • 如下图,例如固定长度10的数组,里面存了两个有效数据,int型变量pointer等于1即可,表示数组的位置1存储着最后一个有效数据,后面再加入新的数据时,放在pointer+1的位置即可
    在这里插入图片描述

最小值问题

  • 题目要求中规定了getMin方法要返回当前栈内的最小值,所以我们要搞清楚什么时候最小值会发生变化:
  1. 栈内增加元素时,可能新增的元素比栈内元素都小
  2. 栈内弹出元素时,可能弹出的元素是最小的那个
  • 对于增加元素时的处理最简单:准备个成员变量min,每次增加元素时,都比较增加的元素和当前min谁最小,最小的更新到min中
  • 但是,弹出时呢?最小值被弹出去了,那么原本次小的就成了最小的,但是次小的咱们没存啊,这时候有两种选择:
  1. 首先,参考官方源码,再准备一个数组,每次增加时,就把最小值放进来
  2. 其次,每次弹出时,再重新算一遍最小值,O(n)的耗时,感觉还好...
  • 斟酌再三,方案一会导致内存翻倍,所以还是优先考虑方案二吧,也就是每次弹出时重新计算一遍最小值

内存怎么优化?

  • 接下来要考虑如何少使用内存
  • 首先要搞清楚的是:准备多大的数组才能满足题目要求,官方说明如下图,注意红色箭头,如果调用三万次push,那就说明会存三万个int数字,所以数组长度如果低于三万,提交后就可能报错,达不到官方要求
    在这里插入图片描述
  • 所以,数组的长度固定是三万吗?
  • 当然不需要,提交代码后,LeetCode会执行多个用例,不可能每个用例都push三万次的,所以固定三万的长度,看似保险,实则浪费
  • 所以,优化思路可以借鉴HashMap的源码:存不下的时候,就扩容,也就是准备一个新数组,把老数组的数据复制进去,至于扩多少?逻辑不必太复杂,翻倍即可

耗时怎么优化

  • 还有最后一个问题要考虑:时间还能优化吗?
  • 要想优化时间,首先咱们要知道哪里会耗时,回顾前面的设计,最耗时的地方应该是弹出元素的时候,这时候要重新计算最小值,时间复杂度是O(n),每次弹出都要执行,有没有可能优化一下呢?
  • 考虑下图这种情况,栈内数据是1、2、3,其中1在栈顶,那么弹出1之后,自然要在2和3中寻找最小值作为栈的最小值了,这是必要操作,不能优化
    在这里插入图片描述
  • 但是下图这种情况呢?3在栈顶,弹出去之后,1还是最小值,此时就没有必要重新比较一遍了
    在这里插入图片描述
  • 好了,分析和设计都完成了,也该写代码验证效果了,我有种预感,自己设计的栈,比LeetCode官方的更快,也更省内存,希望不要被现实打脸...

编码

  • 完整代码如下,有了前面的详细分析,相信您可以轻松看懂,注意我这里数组的初始长度是64,您也可以调整成其他值试试
  1. class MinStack {
  2. private int[] array = new int[64];
  3. private int pointer = -1;
  4. private int min = Integer.MAX_VALUE;
  5. public MinStack() {
  6. }
  7. public void push(int val) {
  8. array[++pointer] = val;
  9. min = Math.min(min, val);
  10. // 扩容
  11. if (pointer==(array.length-1)) {
  12. int[] temp = new int[array.length*2];
  13. System.arraycopy(array, 0, temp, 0, array.length);
  14. array = temp;
  15. }
  16. }
  17. public void pop() {
  18. pointer--;
  19. // 这里可以优化:如果弹出的不是最小值,那就没必要重算呀!
  20. if (array[pointer+1]==min) {
  21. min = Integer.MAX_VALUE;
  22. for (int i=0;i<=pointer;i++) {
  23. min = Math.min(min, array[i]);
  24. }
  25. }
  26. }
  27. public int top() {
  28. return array[pointer];
  29. }
  30. public int getMin() {
  31. return min;
  32. }
  33. }
  • 提交,顺利AC,成绩如下,用时和内存双双优于官方,尤其是用时,击败百分百!
    在这里插入图片描述
  • 至此,第155题顺利完成,自我感觉是有一些收获的,至少比官方的面向API编程收获更大,更何况成绩比官方的还好一些...

欢迎关注博客园:程序员欣宸

学习路上,你不孤单,欣宸原创一路相伴...

原文链接:https://www.cnblogs.com/bolingcavalry/p/17689777.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号