Leetcode 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] <= 10
- nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
C语言题解和思路
int maxProduct(int* nums, int numsSize) {
int i, max = nums[0], min = nums[0], ret = nums[0];
for(i = 1; i < numsSize; i++)
{
if(nums[i] < 0)
{
int tmp = max;
max = min;
min = tmp;
}
max = fmax(max * nums[i], nums[i]);
min = fmin(min * nums[i], nums[i]);
ret = fmax(ret, max);
}
return ret;
}
解题思路
动态规划
乘积的最大子数组和和求子数组最大的和不一样，两个很小的数相乘可能会变成最大的数（负负得正），所以我们不止要记录子数组最大的乘积，还要记录子数组最小的乘积。
将记录最大值的变量 max 、记录最小值的变量 min 、记录返回值的变量 ret ，全部初始化为数组 nums 的第一个数。
从数组的第二个数开始遍历数组，如果该数是负数，交换最大值和最小值。比较该数和最大值与该数的乘积，取更大大值，更新最大值；比较该数与最小值与该数的乘积，取更小值，更新最小值；比较返回值和最大值，更新返回值。
最后返回 ret 。
Leetcode 162. 寻找峰值
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。
提示：
- 1 <= nums.length <= 1000
- -231 <= nums[i] <= 231 - 1
- 对于所有有效的 i 都有 nums[i] != nums[i + 1]
C语言题解和思路
int findPeakElement(int* nums, int numsSize) {
if(numsSize == 1)
{
return 0;
}
int i = 1, max = 0;
while(i + 1 < numsSize)
{
if(nums[i - 1] < nums[i] && nums[i] > nums[i + 1])
{
return i;
}
max = nums[max] > nums[i] ? max : i;
if(nums[i + 1] < nums[i])
{
i += 2;
}
else{
i++;
}
}
max = nums[max] > nums[numsSize - 1] ? max : numsSize - 1;
return max;
}
解题思路
这题在寻找数组中的峰值元素，如果该元素大于左右两边的元素，直接返回该元素下标，如果不存在大于左右两边的元素，返回最大值元素的下标，所以在循环中，我们还同时要记录数组最大值元素的下标。
最大值下标初始化为 0 ，从下标 1 开始遍历数组：判断该下标的元素是否满足条件，如果满足，直接返回该下标；比较值和最大值，记录更大值的下标；判断该元素的下一个元素比该元素小还是大，如果比该元素小， i 前进两步，否则 i 前进一步。
如果循环结束还没有返回任何值，返回最大值的下标。
