[剑指offer]面试题第[59-2]题[JAVA][队列的最大值][暴力][双端队列]

柔光的暖阳◎ 2023-02-26 04:29 11阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 暴力 ######

**复杂度分析**  
![在这里插入图片描述][20200714121007536.png]

class MaxQueue { 
    
        Queue<Integer> queue = new LinkedList();
        int maxValue;
        public MaxQueue() { 
            queue = new LinkedList();
        }
        
        public int max_value() { 
            if(queue.isEmpty()) return -1;
            return maxValue;
        }
        
        public void push_back(int value) { 
            queue.offer(value);
            if(value > maxValue) maxValue = value;
        }
        
        public int pop_front() { 
            if(queue.isEmpty()) return -1;
            int ans = queue.poll();
            if(ans == maxValue){ 
                int size = queue.size();
                if(size == 0){ 
                    maxValue = Integer.MIN_VALUE;
                    return ans;
                }
                maxValue = queue.peek();
                for(int i = 0; i<size; i++)
                    this.push_back(queue.poll());
            }
            return ans;
    
        }
    }

###### 2. 维护一个单调的双端队列 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(1) 空间复杂度：O(N)**  
![在这里插入图片描述][20200714121155150.png]

public class MaxQueue { 
    
        Queue<Integer> queue;
        LinkedList<Integer> max;
        public MaxQueue() { 
            queue = new LinkedList<>();
            max = new LinkedList<>();//LinkedList是双端链表
        }
        
        public int max_value() { 
            return max.size()==0?-1:max.getFirst();
        }
        
        public void push_back(int value) { 
            queue.add(value);
            while(max.size()!=0&&max.getLast()<value){ //注意：这里第二个判断条件不能带等号，即max中对于当前queue中的具有相同值的元素会全部存储，而不是存储最近的那个。
                max.removeLast();
            }
            max.add(value);
        }
        
        public int pop_front() { 
            if(max.size()!=0&&queue.peek().equals(max.getFirst()))//Integer类型的值的比较不能直接使用==
                max.removeFirst();
            return queue.size()==0?-1:queue.poll();
        }
        
        /** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); */
    }

#### 【总结】 ####

###### 1.ArrayList与LinkedList对比 ######

ArrayList是顺序结构，所以定位很快，但插入，删除数据慢。  
LinkedList 是链表结构，定位慢，但插入，删除数据快。

###### 2.ArrayList与LinkedList常见方法 ######

**ArrayList实现了List接口，常见方法有：**  
add(); contains(); get(); indexOf():定位对象所处的位置; remove(); size(); toArray(); toString();//转换为字符串

**LinkedList也实现了List接口外，可以实现上述ArrayList中的常用方法，此外：**  
1.LinkedList还实现了**双向链表结构Deque**，可以很方便的在头尾插入删除数据。  
LinkedList link = new LinkedList<>();  
常用方法：  
addFirst(); addLast();  
getFirst(); getLast();  
removeFirst(); removeLast();

2.LinkedList除了实现了List和Deque外，还实现了**Queue接口(队列)**,  
**Queue是先进先出队列 FIFO**。  
Queue< class > queue = new LinkedList<>();  
常用方法：  
poll()取出第一个元素;  
peek()查看第一个元素;  
offer()在最后添加元素,可用add()替换;  
**扩展**  
**先进后出FILO Stack栈**：  
Stack stack = new Stack<>();  
常用方法：  
push();可用add();代替  
pop();输出末尾的元素相当于LinkedList中的removeLast();  
peek();查看最后一个元素，相当于getLast();

###### 3.做题需要不断总结整理归纳 ######

建议和\[剑指offer\]\[JAVA\]面试题第\[09\]题\[用两个栈实现队列\]LinkedList(https://blog.csdn.net/dadongwudi/article/details/106478719)一起学习

参考链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-ii-javashi-xian-yuan-li-he-mian-shi/  
参考链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/qi-shi-bu-tai-li-jie-jun-tan-fu-za-du-by-acnesu/  
参考链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-ii-dui-lie-de-zui-da-zhi-by-leetcod/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/75d8b0018e174aa4a3f651e559415806.png
[20200714121007536.png]: https://img-blog.csdnimg.cn/20200714121007536.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020071412111277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200714121155150.png]: https://img-blog.csdnimg.cn/20200714121155150.png