题目地址
https://leetcode.com/problems/maximum-product-subarray/description/
题目描述
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
思路
这道题目的通过率非常低
这道题目要我们求解连续的 n 个数中乘积最大的积是多少。这里提到了连续,笔者首先
想到的就是滑动窗口,但是这里比较特殊,我们不能仅仅维护一个最大值,因此最小值(比如-20)乘以一个比较小的数(比如-10)
可能就会很大。 因此这种思路并不方便。
首先来暴力求解,我们使用两层循环来枚举所有可能项,这种解法的时间复杂度是O(n^2), 代码如下:
var maxProduct = function(nums) { let max = nums[0]; let temp = null; for (let i = 0; i < nums.length; i++) { temp = nums[i]; max = Math.max(temp, max); for (let j = i + 1; j < nums.length; j++) { temp *= nums[j]; max = Math.max(temp, max); } } return max; };
因此我们需要同时记录乘积最大值和乘积最小值,然后比较元素和这两个的乘积,去不断更新最大值。
这种思路的解法由于只需要遍历一次,其时间复杂度是O(n),代码见下方代码区。
关键点
- 同时记录乘积最大值和乘积最小值
代码
/* * @lc app=leetcode id=152 lang=javascript * * [152] Maximum Product Subarray * * https://leetcode.com/problems/maximum-product-subarray/description/ * * algorithms * Medium (28.61%) * Total Accepted: 202.8K * Total Submissions: 700K * Testcase Example: '[2,3,-2,4]' * * Given an integer array nums, find the contiguous subarray within an array * (containing at least one number) which has the largest product. * * Example 1: * * * Input: [2,3,-2,4] * Output: 6 * Explanation: [2,3] has the largest product 6. * * * Example 2: * * * Input: [-2,0,-1] * Output: 0 * Explanation: The result cannot be 2, because [-2,-1] is not a subarray. * */ /** * @param {number[]} nums * @return {number} */ var maxProduct = function(nums) { let max = nums[0]; let min = nums[0]; let res = nums[0]; for (let i = 1; i < nums.length; i++) { let tmp = min; min = Math.min(nums[i], Math.min(max * nums[i], min * nums[i])); // 取最小 max = Math.max(nums[i], Math.max(max * nums[i], tmp * nums[i])); /// 取最大 res = Math.max(res, max); } return res; };LeetCode题解104.maximum-depth-of-binary-tree
题目地址 https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the lo…
LeetCode题解1310.xor-queries-of-a-subarray题目地址(1310. 子数组异或查询) https://leetcode-cn.com/problems/xor-queries-of-a-subarray 题目描述 有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。 对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr…
LeetCode题解1297.maximum-number-of-occurrences-of-a-substring题目地址(1297. 子串的最大出现次数) https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数: 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…
LeetCode题解1186.maximum-subarray-sum-with-one-deletion题目地址 https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ 题目描述 给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。 换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦)…
LeetCode题解124.binary-tree-maximum-path-sum题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…