更新时间：2025-04-06
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2*10^4-10 <= nums[i] <= 10nums 的任何子数组的乘积都 保证 是一个 32-位 整数
方法：动态规划
使用动态规划维护两个变量 currentMax 和 currentMin，分别表示以当前元素结尾的子数组的最大和最小乘积。通过遍历数组，每一步利用前一步的状态更新当前值，并记录全局最大值。
-
初始化
currentMax和currentMin初始化为第一个元素的值。globalMax记录全局最大乘积，初始值也为第一个元素。
-
遍历数组
- 对于每个元素
num，计算三种可能的乘积：- 当前元素本身（可能作为新子数组的起点）。
- 当前元素乘以前一个最大乘积
currentMax * num。 - 当前元素乘以前一个最小乘积
currentMin * num（负数可能反转结果）。
- 更新
currentMax和currentMin为三种情况中的最大值和最小值。
- 对于每个元素
-
更新全局最大值
- 每次迭代后比较
globalMax和当前currentMax，确保记录全局最优解。
- 每次迭代后比较
代码实现(Java)：
class Solution {public int maxProduct(int[] nums) {if (nums.length == 0) return 0;int currentMax = nums[0];int currentMin = nums[0];int globalMax = nums[0];for (int i = 1; i < nums.length; i++) {int num = nums[i];// 保存临时值，防止覆盖导致的计算错误int tempMax = Math.max(num, Math.max(currentMax * num, currentMin * num));int tempMin = Math.min(num, Math.min(currentMax * num, currentMin * num));currentMax = tempMax;currentMin = tempMin;globalMax = Math.max(globalMax, currentMax);}return globalMax;}
}
复杂度分析
- 时间复杂度：
O(n)，只需一次遍历数组。 - 空间复杂度：
O(1)，仅用常数空间存储状态变量。
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums 中的所有整数互不相同nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
方法：二分查找法
通过比较中间元素与右边界元素，判断最小值所在区间，逐步缩小搜索范围。
- 旋转特性分析：旋转后的数组由两个递增子数组组成，最小值位于第二个子数组的首位；
- 关键比较逻辑：
- 当
nums[mid] > nums[right]时，说明右半部分存在更小元素，收缩左边界； - 当
nums[mid] <= nums[right]时，说明右半部分有序，最小值可能在左侧或当前mid位置；
- 当
- 终止条件：当左右指针相遇时，指向的位置即为最小值所在。
代码实现(Java)：
class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {// 最小值在右半部分left = mid + 1;} else {// 最小值在左半部分（含mid）right = mid;}}return nums[left];}
}
复杂度分析
- 时间复杂度
O(log n)，每次循环将搜索范围减半。 - 空间复杂度
O(1)，仅需常数级额外空间。
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.
提示：
-2^31 <= val <= 2^31 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3*10^4 次
方法：双栈同步维护法
使用主栈存储元素，辅助栈同步存储对应状态下的最小值，实现所有操作O(1)时间复杂度。
-
双栈同步机制：
- 主栈
dataStack正常执行栈操作； - 辅助栈
minStack存储对应主栈状态时的最小值； - 每次push操作同步更新两个栈，保证栈高度一致。
- 主栈
-
最小值维护策略：
- 当新元素入栈时，
minStack压入min(新元素, 当前minStack栈顶)； - 当元素出栈时，双栈同步弹出保持状态一致。
- 当新元素入栈时，
代码实现(Java)：
class MinStack {private Deque<Integer> dataStack; // 主栈存储元素private Deque<Integer> minStack; // 辅助栈存储最小值public MinStack() {dataStack = new ArrayDeque<>();minStack = new ArrayDeque<>();}public void push(int val) {dataStack.push(val);// 维护最小值：如果辅助栈为空直接压入，否则取当前值与栈顶较小值if (minStack.isEmpty()) {minStack.push(val);} else {minStack.push(Math.min(val, minStack.peek()));}}public void pop() {dataStack.pop();minStack.pop();}public int top() {return dataStack.peek();}public int getMin() {return minStack.peek();}
}
复杂度分析
- 时间复杂度：
push、pop、top、getMin操作均为O(1)。 - 空间复杂度：
O(n)，每个元素对应存储一个最小值记录。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。