个人如何做购物网站 关于支付接口,龙口网络公司,上海建设集团有限公司,施工企业安全生产管理体系案例文章目录 Leetcode 152. 乘积最大子数组题目描述C语言题解和思路解题思路 Leetcode 162. 寻找峰值题目描述C语言题解和思路解题思路 Leetcode 152. 乘积最大子数组
题目描述
给你一个整数数组 nums #xff0c;请你找出数组中乘积最大的非空连续子数组#xff08;该子数组中… 文章目录 Leetcode 152. 乘积最大子数组题目描述C语言题解和思路解题思路 Leetcode 162. 寻找峰值题目描述C语言题解和思路解题思路 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] 10nums 的任何前缀或后缀的乘积都 保证 是一个 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 前进一步。
如果循环结束还没有返回任何值返回最大值的下标。
