max element Archives - Huahua's Tech Road

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

By zxi on May 31, 2020

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Solution 1: Sort

We want to find the largest and second largest elements.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

return (nums[0] - 1) * (nums[1] - 1);

}

};

Solution 2: Without sorting

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int m1 = 0;

int m2 = 0;

for (int n : nums) {

if (n > m1) {

m2 = m1;

m1 = n;

} else if (n > m2) {

m2 = n;

}

return (m1 - 1) * (m2 - 1);

}

};

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

By zxi on March 5, 2018

题目大意：给你一棵树，返回每一层最大的元素的值。

You need to find the largest value in each row of a binary tree.

Example:

<b>Input:</b>

/ \

3 2

/ \ \

5 3 9

<b>Output:</b> [1, 3, 9]

Solution 1: Inorder traversal + depth info

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> ans;

inorder(root, 0, ans);

return ans;

}

private:

void inorder(TreeNode* root, int d, vector<int>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back(INT_MIN);

inorder(root->left, d + 1, ans);

ans[d] = max(ans[d], root->val);

inorder(root->right, d + 1, ans);

}

};

Python3

"""

Author: Huahua

Running time: 72 ms (beats 100%)

"""

class Solution:

def largestValues(self, root):

def inorder(root, d, ans):

if not root: return ans

if len(ans) <= d: ans += [float('-inf')]

inorder(root.left, d + 1, ans)

if root.val > ans[d]: ans[d] = root.val

inorder(root.right, d + 1, ans)

return ans

return inorder(root, 0, [])

花花酱 LeetCode 795. Number of Subarrays with Bounded Maximum

By zxi on March 3, 2018

题目大意：问一个数组中有多少个子数组的最大元素值在[L, R]的范围里。

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :

Input:

A = [2, 1, 4, 3]

L = 2

R = 3

Output: 3

Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Solution 1:

C++

// Author: Huahua

// Running time: 42 ms

class Solution {

public:

int numSubarrayBoundedMax(vector<int>& A, int L, int R) {

return count(A, R) - count(A, L - 1);

}

private:

// Count # of sub arrays whose max element is <= N

int count(const vector<int>& A, int N) {

int ans = 0;

int cur = 0;

for (int a: A) {

if (a <= N)

ans += ++cur;

else

cur = 0;

}

return ans;

}

};

Solution 2: One pass

C++

// Author: Huahua

// Running time: 38 ms

class Solution {

public:

int numSubarrayBoundedMax(vector<int>& A, int L, int R) {

int ans = 0;

int left = -1;

int right = -1;

for (int i = 0; i < A.size(); ++i) {

if (A[i] >= L) right = i;

if (A[i] > R) left = i;

ans += (right - left);

}

return ans;

}

};

Posts tagged as “max element”

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

Solution 1: Sort

C++

Solution 2: Without sorting

C++

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

花花酱 LeetCode 795. Number of Subarrays with Bounded Maximum