LeetCode热题 HOT100：排序链表、乘积最大子数组、最小栈
LeetCode热题 HOT100
148. 排序链表
题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
**示例 1： {
// 如果传入的头节点为空，直接返回null
if (head == null) {
return null;
}
// 创建一个PriorityQueue对象，用于存储链表中的节点，并按照节点的值进行排序
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
// 将链表中的所有节点依次添加到PriorityQueue中
while (head != null) {
queue.add(head);
head = head.next;
}
// 从PriorityQueue中取出第一个节点作为新链表的头结点，并将其赋值给一个新的指针变量newHead
ListNode newHead = queue.poll();
// 创建一个指针变量cur，用于记录新链表的末尾节点
ListNode cur = newHead;
// 从PriorityQueue中依次取出节点，并将其添加到新链表的末尾
while (queue.size() > 0) {
cur.next = queue.poll();
cur = cur.next;
}
// 最后将新链表的末尾节点的next指针设置为null，以便将其作为链表的结尾返回
cur.next = null;
return newHead;
}
}
152. 乘积最大子数组
题目：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），
并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
**示例 1：
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
思路分析： 使创建两个长度与原数组相同的数组maxRes和minRes，分别用于存储到目前为止的最大值和最小值。初始化res为nums[0]，maxRes[0]和minRes[0]均为nums[0]。从数组的第二个元素开始循环遍历整个数组，对于每个元素，计算出到目前为止的最大值和最小值，并将其分别存储到maxRes和minRes数组中。更新最终结果res，即为maxRes数组中的最大值。返回最终结果res。
class Solution {
public int maxProduct(int[] nums) {
// 如果传入的数组为空或长度为0，直接返回0
if(nums == null || nums.length == 0){
return 0;
}
// 创建两个长度与原数组相同的数组maxRes和minRes，分别用于存储到目前为止的最大值和最小值
int[] maxRes = new int[nums.length];
int[] minRes = new int[nums.length];
// 初始化res为nums[0]，maxRes[0]和minRes[0]均为nums[0]
int res = nums[0];
maxRes[0] = nums[0];
minRes[0] = nums[0];
// 从数组的第二个元素开始循环遍历整个数组
for(int i = 1; i < nums.length; i++){
// 计算出到目前为止的最大值和最小值，并将其分别存储到maxRes和minRes数组中
maxRes[i] = Math.max(nums[i], Math.max(maxRes[i - 1] * nums[i], minRes[i - 1] * nums[i]));
minRes[i] = Math.min(nums[i], Math.min(maxRes[i - 1] * nums[i], minRes[i - 1] * nums[i]));
// 更新最终结果res，即为maxRes数组中的最大值
res = Math.max(res, maxRes[i]);
}
// 返回最终结果res
return res;
}
}
155. 最小栈
题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 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.
思路分析： 创建两个栈stack1和stack2，其中stack1用于存储元素，stack2用于存储当前栈中的最小值。push方法：每次往stack1中添加元素时，同时判断该元素是否小于等于stack2栈顶元素，如果是，则将该元素也压入stack2中，否则不做操作。pop方法：每次从stack1中弹出元素时，同时判断该元素是否等于stack2栈顶元素，如果是，则将该元素也从stack2中弹出，否则不做操作。top方法：返回stack1栈顶元素。getMin方法：返回stack2栈顶元素，即为当前栈中的最小值。整体思路：使用辅助栈stack2记录当前栈中的最小值。每次压入元素时，如果该元素小于等于stack2栈顶元素，则将该元素同步压入stack2中；每次弹出元素时，如果该元素等于stack2栈顶元素，则在stack2中也将其弹出。这样，stack2中始终存储的是当前栈中的最小值，可以在常数时间内获取。
class MinStack {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MinStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
// 往栈中添加元素，同时更新最小值栈stack2
public void push(int val) {
stack1.push(val); // 将元素压入stack1中
// 如果stack2为空，或者新元素小于等于最小值栈的栈顶元素，将新元素压入最小值栈
if(stack2.isEmpty() || val <= stack2.peek()){
stack2.push(val);
}
}
// 从栈中弹出元素，同时更新最小值栈stack2
public void pop() {
// 如果stack1的栈顶元素等于stack2的栈顶元素，说明stack1的栈顶元素为最小值，同时更新最小值栈stack2
if(stack1.peek().equals(stack2.peek())){
stack2.pop();
}
// 弹出stack1的栈顶元素
stack1.pop();
}
// 返回栈顶元素
public int top() {
return stack1.peek();
}
// 返回最小值栈的栈顶元素，即为当前栈中的最小值
public int getMin() {
return stack2.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
原文地址：https://blog.csdn.net/weixin_51405802/article/details/130196583
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！