題目敘述
題目會給定一個整數陣列nums，要求我們找出最大的兩個整數a, b，返回(a-1) * (b-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 <= 5001 <= nums[i] <= 10^3
演算法
第一直覺可能會想到先排序，再取最大的前兩個數字。
但是，其實不用排序，我們需要的只有前兩個最大的元素，分別用兩個變數first, second去記錄最大值 和 第二大的值，分別減一再相乘即可。
程式碼
cclass Solution(object):
def maxProduct(self, nums):
first, second = 0, 0
for number in nums:
if number > first:
# update first largest and second largest
first, second = number, first
elif number > second:
# update second largest
second = number
return (first - 1) * (second - 1)
複雜度分析
時間複雜度:
O( n ) 一次從左到右的線性掃描，長度和原本的陣列一樣長。
空間複雜度:
O( 1 ) 使用到的是固定大小的臨時變數，所佔用空間為常數級別。
關鍵知識點:
陣列的輸入資料打散的前提下，當所求為前K大或前K小的元素時，
聯想到O(n)時間的線性掃描演算法。
不需要真的去排序，省下整個陣列排序的成本O(n log n)。
Reference:
