LeetCode 腾讯精选50题--最小栈

骑猪看日落 2023-06-05 05:53 17阅读 0赞

题目很简单，实现一个最小栈，能够以线形的时间获取栈中元素的最小值

自己的思路如下：

利用数组，以及两个变量， last用于记录栈顶元素的位置，min用于记录栈中元素的最小值；

每一次push，都比较min与x的大小，其次，push操作执行时若数组已满，这需要进行扩容，将数组长度扩大为原来的两倍，并进行数组的迁移。每一次 pop 时，若删除的是最小元素，则遍历数组重新找到最小的元素，然后删除栈顶元素。

时间分析：

push: 最坏情况为O(n),其余为O(1)

pop：最坏情况:O(n)，其余为O(1)

top:O(1)

getMin: O(1)

以下是代码：

private int[] array;
        private int last;
        private int min;
        public MinStack() {
            array = new int[16];
            last=0;
            min = 0;
        }
    
        public void push(int x) {
            if(last >= array.length){
                this.array = expand(this.array);
            }
            array[last++] = x;
            if(min > x || last==1){
                this.min = x;
            }
        }
        public void pop() {
            if(last -1 <0){
                return;
            }
            if(this.min == array[last-1]){
                this.min = findMin(array,last-1);
            }
            this.last = this.last - 1;
            this.last = this.last < 0 ? 0:this.last;
        }
    
        public int top() {
            if(last -1 <0){
                return 0;
            }
            int result = this.array[last-1];
            return result;
        }
    
        public int getMin() {
            return this.min;
        }
    
        private int[] expand(int[] array){
    
            int[] tempArray = new int[array.length*2];
            for (int i=0;i<array.length;i++){
                tempArray[i] = array[i];
            }
    
            return tempArray;
        }
    
        private int findMin(int array[],int last){
    
            if(last <=0){
                return 0;
            }
            int tempMin = array[last-1];
            for (int i=last-1;i>=0;i--){
                tempMin = Math.min(array[i],tempMin);
            }
            return tempMin;
    
        }

\--------------------------------------------------------我是分割线----------------------------------------------------------------------------

好了，经过讨论学习，学会了一种新的解法：

在上面介绍的基础上在添加一个公式：

首先先介绍一下 一个公式：2\*x-minEle\_1 < x 其中 x是当前插入的值，minEle\_1 是x插入前的最小值

详细思路如下：

入栈：

1.使用一个变量minEle 记录当前栈中的元素 （是真实值）

2.每一次插入一个元素x，比较 x 与 minEle，有如下两种情况：

1)、若x > = minEle，那么直接push进栈，minEle不变

2)、若x < minEle，那么执行以下操作：

a、首先计算要入栈的虚拟值y：y=2\*x - minEle ，y入栈（注意此处y不是真实值，但是可以肯定 y < x 原因：因为x < minEle 故 x-minEle < 0 ; x+一个小于0的值一定小于x）

b、其次更新minEle 为 x

以上步骤只为保存前一个最小的值。

出栈：

1、出栈前，比较当前出栈的值Y，存在两种情况：

1）、若Y > minEle 那么直接出栈

2）、若 Y < minEle，那么要执行如下操作：

a、X = 2\*minEle - Y ,

b、讲 minEle出栈，同事更新minEle= X

以上步骤用于还原前一次的最小值

根据此算法可以保证 更新minEle的时间复杂度为O(1),弥补了之前自己想法上的不足，同时又不需要使用另一个辅助栈，节约了空间（虽然空间复杂度都是O(N)，但是O(N) 与 O(2N)还是有差别的）

以下是写的代码：（注意：由于int 最大值为 2147483647 最小值为 -2147483648 ，所以需要针对极限值做一次单独的转换：

入栈：

当 x - Integer.MIN\_VALUE < minEle 时：

int record = last; (此处记录特殊处理的位置，当到此位置时另行处理)

int reminder = minEle % 10 (保存余数);

设Y为要存入的值：Y = x/10 \*2 - minEle/10 ，然后将Y入栈

出栈：

判断当前位置 last == record:

若是 ： minEle = (x/10 \*2 - 当前出栈的值)\*10 + reminder

判断当前出栈元素是否小于 minEle

若是： minEle = (x\*2 - 当前出栈的值）

否则直接出栈，无需操作

1 package algorithm;
      2 import java.util.Stack;
      3 
      4 public class MinStack {
      5 
      6     private int[] array;
      7 
      8     private int last;
      9 
     10     private int min;
     11 
     12     private int record;
     13 
     14     private int min_remainder;
     15 
     16     public MinStack() {
     17         array = new int[16];
     18         last=0;
     19         min = 0;
     20         record=-1;
     21         min_remainder = -1;
     22     }
     23 
     24     public void push(int x) {
     25         if(last >= array.length){
     26             this.array = expand(this.array);
     27         }
     28         if(last==0){
     29             this.min = x;
     30             array[last++] = x;
     31         }else if(this.min > x){
     32             if(x - (Integer.MIN_VALUE+1) < this.min){
     33                 array[last++] = createVirtual(x);
     34             }else {
     35                 array[last++] = (x<<1) - this.min;
     36             }
     37             this.min = x;
     38 
     39         }else {
     40             array[last++] = x;
     41         }
     42     }
     43 
     44     public void pop() {
     45         if(last -1 <0){
     46             return;
     47         }
     48         if(record == last){
     49             this.min = (this.min/10 - array[last-1] + this.min/10)*10+min_remainder;
     50         }else {
     51             if(array[last-1] < this.min){
     52                 int temp = this.min<<1 - array[last-1];
     53                 this.min = temp;
     54             }
     55         }
     56         this.last = this.last - 1;
     57         this.last = this.last < 0 ? 0:this.last;
     58     }
     59 
     60     public int top() {
     61         if(last -1 <0){
     62             return 0;
     63         }
     64         int result = 0;
     65         if(record == last || array[last-1] < this.min){
     66             result = this.min;
     67         }else {
     68             result = this.array[last-1];
     69         }
     70         return result;
     71     }
     72 
     73     public int getMin() {
     74         return this.min;
     75     }
     76 
     77     private int[] expand(int[] array){
     78         int[] tempArray = new int[array.length*2];
     79         for (int i=0;i<array.length;i++){
     80             tempArray[i] = array[i];
     81         }
     82         return tempArray;
     83     }
     84 
     85     private int createVirtual(int x){
     86         int temp = 0;
     87         if(x - (Integer.MIN_VALUE+1) < this.min){
     88             record = this.last;
     89             min_remainder = this.min%10;
     90             temp = x/10 - this.min/10 + x/10;
     91 
     92             return temp;
     93         }else {
     94             temp = x << 1 - this.min;
     95         }
     96 
     97         return temp;
     98     }
     99 
    100     public static void main(String[] args){
    101         MinStack min = new MinStack();
    102         min.push(2147483646);
    103         min.push(2147483646);
    104         min.push(2147483647);
    105         min.top();
    106         min.pop();
    107         System.out.println("min:"+min.getMin());
    108         min.pop();
    109         System.out.println("min:"+min.getMin());
    110         min.pop();
    111         min.push(2147483647);
    112         min.top();
    113         min.push(-2147483648);
    114         System.out.println("top"+min.top());
    115         System.out.println("min:"+min.getMin());
    116         min.pop();
    117         System.out.println("min:"+min.getMin());
    118 
    119 
    120     }
    121 
    122 }

转载于:https://www.cnblogs.com/Kaithy-Rookie/p/11296064.html