合併兩個有序數組#
給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。
請你 合併 nums2 到 nums1 中，使合併後的數組同樣按 非遞減順序 排列。
注意：最終，合併後數組不應由函數返回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0 ，應忽略。nums2 的長度為 n 。
示例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合併 [1,2,3] 和 [2,5,6] 。
合併結果是 [1,2,2,3,5,6] ，其中斜體加粗標註的為 nums1 中的元素。
示例 2：
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合併 [1] 和 [] 。
合併結果是 [1] 。
示例 3：
輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合併的數組是 [] 和 [1] 。
合併結果是 [1] 。
注意，由於 m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合併結果可以順利存放到 nums1 中。
class Solution:
def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i, j = m - 1, n - 1
k = len(nums1) - 1
while (i >= 0 and j >= 0):
if (nums1[i] > nums2[j]):
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
if (i == -1):
for i in range(0, j+1):
nums1[i] = nums2[i]
移除元素#
給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等於 val 的元素，並返回移除後數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並 原地 修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
示例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。你不需要考慮數組中超出新長度後面的元素。例如，函數返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。
示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮數組中超出新長度後面的元素。
class Solution:
def removeElement(self, nums: list[int], val: int) -> int:
i, j = 0, len(nums)
while (i < j):
if (nums[i] == val):
j -= 1
nums[i] = nums[j]
else:
i += 1
return j
刪除有序數組中的重複項#
給你一個 升序排列 的數組 nums ，請你 ** 原地** 刪除重複出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。元素的 相對順序 應該保持 一致 。然後返回 nums 中唯一元素的個數。
考慮 nums 的唯一元素的數量為 k ，你需要做以下事情確保你的題解可以被通過：
- 更改數組
nums，使nums的前k個元素包含唯一元素，並按照它們最初在nums中出現的順序排列。nums的其餘元素與nums的大小不重要。 - 返回
k。
示例 1：
輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_]
解釋：函數應該返回新的長度 2 ，並且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度後面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該返回新的長度 5 ， 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數組中超出新長度後面的元素。
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
j = 0
for i in range(1, len(nums)):
if (nums[i] != nums[j]):
nums[j + 1] = nums[i]
j += 1
return j + 1
刪除有序數組中的重複項 II#
給你一個有序數組 nums ，請你 ** 原地** 刪除重複出現的元素，使得出現次數超過兩次的元素只出現兩次 ，返回刪除後數組的新長度。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O (1) 額外空間的條件下完成。
示例 1：
輸入：nums = [1,1,1,2,2,3]
輸出：5, nums = [1,1,2,2,3]
解釋：函數應返回新長度 length = 5, 并且原數組的前五個元素被修改為 1, 1, 2, 2, 3 。 不需要考慮數組中超出新長度後面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,1,2,3,3]
輸出：7, nums = [0,0,1,1,2,3,3]
解釋：函數應返回新長度 length = 7, 并且原數組的前五個元素被修改為 0, 0, 1, 1, 2, 3, 3 。 不需要考慮數組中超出新長度後面的元素。
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
if (len(nums) <= 2):
return len(nums)
i = 1
for j in range(2, len(nums)):
if (nums[j] != nums[i] or nums[j] == nums[i] and nums[j] != nums[i-1]):
nums[i + 1] = nums[j]
i += 1
return i + 1
多數元素#
給定一個大小為 n 的數組 nums ，返回其中的多數元素。多數元素是指在數組中出現次數 大於 ⌊ n/2 ⌋ 的元素。
你可以假設數組是非空的，並且給定的數組總是存在多數元素。
示例 1：
輸入：nums = [3,2,3]
輸出：3
示例 2：
輸入：nums = [2,2,1,1,1,2,2]
輸出：2
class Solution:
def majorityElement(self, nums: list[int]) -> int:
count = 0
res = nums[0]
for num in nums:
if (count == 0 or res == num):
res = num
count += 1
else:
count -= 1
return res
輪轉數組#
給定一個整數數組 nums，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。
示例 1:
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]
class Solution:
def rotate(self, nums: list[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(nums, start, end):
while (start < end):
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
k = k % len(nums)
reverse(nums, 0, len(nums) - k - 1)
reverse(nums, len(nums) - k, len(nums)-1)
reverse(nums, 0, len(nums)-1)
買賣股票的最佳時機#
給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。
你只能選擇 某一天 買入這只股票，並選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。
示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）時買入，在第 5 天（股票價格 = 6）時賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大於買入價格；同時，你不能在買入前賣出股票。
示例 2：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。
class Solution:
def maxProfit(self, prices: list[int]) -> int:
minprice = int(1e9)
maxprofit = 0
for price in prices:
maxprofit = max(price - minprice, maxprofit)
minprice = min(price, minprice)
return maxprofit
跳躍遊戲#
給定一個非負整數數組 nums ，你最初位於數組的 第一個下標 。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最後一個下標。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然後再從下標 1 跳 3 步到達最後一個下標。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最後一個下標。
class Solution:
def canJump(self, nums: list[int]) -> bool:
n, rightmost = len(nums), 0
for i in range(n):
if (i <= rightmost):
rightmost = max(rightmost, i + nums[i])
if (rightmost >= n-1):
return True
return False
跳躍遊戲 II#
給定一個長度為 n 的 0 索引 整數數組 nums。初始位置為 nums[0]。
每個元素 nums[i] 表示從索引 i 向前跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:
0 <= j <= nums[i]i + j < n
返回到達 nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最後一個位置的最小跳躍數是 2。
從下標為 0 跳到下標為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
class Solution:
def jump(self, nums: list[int]) -> int:
n = len(nums)
rightmost, end, step = 0, 0, 0
for i in range(n-1):
if (rightmost >= i):
rightmost = max(rightmost, i + nums[i])
if (i == end):
end = rightmost
step += 1
return step
除自身以外數組的乘積#
給你一個整數數組 nums，返回 數組 answer ，其中 answer[i] 等於 nums 中除 nums[i] 之外其餘各元素的乘積 。
題目數據 保證 數組 nums之中任意元素的全部前綴元素和後綴的乘積都在 32 位 整數範圍內。
請 ** 不要使用除法，** 且在 O(*n*) 時間複雜度內完成此題。
示例 1:
輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]
示例 2:
輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]
class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
left = [1 for _ in nums]
right = [1 for _ in nums]
for i in range(1, len(nums)):
left[i] = nums[i-1] * left[i-1]
for i in range(len(nums)-2, -1, -1):
right[i] = nums[i+1] * right[i+1]
return [left[i] * right[i] for i in range(len(nums))]
接雨水#
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。
示例 1：
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。
示例 2：
輸入：height = [4,2,0,3,2,5]
輸出：9
class Solution:
def trap(self, height: list[int]) -> int:
if (len(height) <= 2):
return 0
lmax = [0 for _ in height]
rmax = [0 for _ in height]
for i in range(1, len(height)-1):
lmax[i] = max(lmax[i-1], height[i-1])
for i in range(len(height)-2, 0, -1):
rmax[i] = max(rmax[i+1], height[i+1])
res = 0
for i in range(1, len(height) - 1):
if (min(lmax[i], rmax[i]) - height[i] > 0):
res += (min(lmax[i], rmax[i]) - height[i])
return res
羅馬數字轉整數#
羅馬數字包含以下七種字符: I， V， X， L，C，D 和 M。
字符 數值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數字 2 寫做 II ，即為兩個並列的 1 。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。
通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規則只適用於以下六種情況：
I可以放在V(5) 和X(10) 的左邊，來表示 4 和 9。X可以放在L(50) 和C(100) 的左邊，來表示 40 和 90。C可以放在D(500) 和M(1000) 的左邊，來表示 400 和 900。
給定一個羅馬數字，將其轉換成整數。
示例 1:
輸入: s = "III"
輸出: 3
示例 2:
輸入: s = "IV"
輸出: 4
示例 3:
輸入: s = "IX"
輸出: 9
示例 4:
輸入: s = "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.
示例 5:
輸入: s = "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
class Solution:
SYMBOL_VALUES = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
def romanToInt(self, s: str) -> int:
ans = 0
n = len(s)
for i, ch in enumerate(s):
val = Solution.SYMBOL_VALUES[ch]
if ((i < n-1) and val < Solution.SYMBOL_VALUES[s[i+1]]):
ans -= val
else:
ans += val
return ans
整數轉羅馬數字#
羅馬數字包含以下七種字符： I， V， X， L，C，D 和 M。
字符 數值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數字 2 寫做 II ，即為兩個並列的 1。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。
通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規則只適用於以下六種情況：
I可以放在V(5) 和X(10) 的左邊，來表示 4 和 9。X可以放在L(50) 和C(100) 的左邊，來表示 40 和 90。C可以放在D(500) 和M(1000) 的左邊，來表示 400 和 900。
給你一個整數，將其轉為羅馬數字。
示例 1:
輸入: num = 3
輸出: "III"
示例 2:
輸入: num = 4
輸出: "IV"
示例 3:
輸入: num = 9
輸出: "IX"
示例 4:
輸入: num = 58
輸出: "LVIII"
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: num = 1994
輸出: "MCMXCIV"
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
class Solution:
VALUE_SYMBOLS = [
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
]
def intToRoman(self, num: int) -> str:
res = []
for val, symbol in Solution.VALUE_SYMBOLS:
while (num >= val):
res.append(symbol)
num -= val
if (num == 0):
break
return ''.join(res)
最後一個單詞的長度#
給你一個字符串 s，由若干單詞組成，單詞前後用一些空格字符隔開。返回字符串中 最後一個 單詞的長度。
單詞 是指僅由字母組成、不包含任何空格字符的最大子字符串。
示例 1：
輸入：s = "Hello World"
輸出：5
解釋：最後一個單詞是“World”，長度為5。
示例 2：
輸入：s = " fly me to the moon "
輸出：4
解釋：最後一個單詞是“moon”，長度為4。
示例 3：
輸入：s = "luffy is still joyboy"
輸出：6
解釋：最後一個單詞是長度為6的“joyboy”。
class Solution:
def lengthOfLastWord(self, s: str) -> int:
r = len(s)-1
while (s[r] == ' '):
r -= 1
i = r
while (i >= 0 and s[i] != ' '):
i -= 1
return r-i
最長公共前綴#
編寫一個函數來查找字符串數組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 ""。
示例 1：
輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：
輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
if (len(strs) == 1):
return "".join(strs)
ans = ""
minLength = 300
for s in strs:
minLength = min(minLength, len(s))
for i in range(minLength):
c = strs[0][i]
print(c)
for j in range(len(strs)):
if (strs[j][i] != c):
return ans
ans += c
return ans
反轉字符串中的單詞#
給你一個字符串 s ，請你反轉字符串中 單詞 的順序。
單詞 是由非空格字符組成的字符串。s 中使用至少一個空格將字符串中的 單詞 分隔開。
返回 單詞 順序顛倒且 單詞 之間用單個空格連接的結果字符串。
** 注意：** 輸入字符串 s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。
示例 1：
輸入：s = "the sky is blue"
輸出："blue is sky the"
示例 2：
輸入：s = " hello world "
輸出："world hello"
解釋：反轉後的字符串中不能存在前導空格和尾隨空格。
示例 3：
輸入：s = "a good example"
輸出："example good a"
解釋：如果兩個單詞間有多餘的空格，反轉後的字符串需要將單詞間的空格減少到僅有一個。
class Solution:
def reverseWords(self, s: str) -> str:
ans = []
end, start = 0, 0
i = len(s) - 1
while (i >= 0):
if (s[i] == " "):
i -= 1
continue
end = i + 1
while (s[i] != " " and i >= 0):
i -= 1
start = i + 1
ans.append(s[start: end])
return ' '.join(ans)
N 字形變換#
將一個給定字符串 s 根據給定的行數 numRows ，以從上往下、從左到右進行 Z 字形排列。
比如輸入字符串為 "PAYPALISHIRING" 行數為 3 時，排列如下：
P A H N
A P L S I I G
Y I R
之後，你的輸出需要從左往右逐行讀取，產生出一個新的字符串，比如："PAHNAPLSIIGYIR"。
請你實現這個將字符串進行指定行數變換的函數：
string convert(string s, int numRows);
示例 1：
輸入：s = "PAYPALISHIRING", numRows = 3
輸出："PAHNAPLSIIGYIR"
示例 2：
輸入：s = "PAYPALISHIRING", numRows = 4
輸出："PINALSIGYAHRPI"
解釋：
P I N
A L S I G
Y A H R
P I
示例 3：
輸入：s = "A", numRows = 1
輸出："A"
class Solution:
def convert(self, s: str, numRows: int) -> str:
if (numRows == 1):
return s
res = ["" for _ in range(numRows)]
step = -1
i, j = 0, 0
while (i < len(s)):
if (j == 0 or j == numRows-1):
step = 0 - step
res[j] += s[i]
j += step
i += 1
return ''.join(res)
找出字符串中第一個匹配項的下標#
給你兩個字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標（下標從 0 開始）。如果 needle 不是 haystack 的一部分，則返回 -1 。
示例 1：
輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標 0 和 6 處匹配。
第一個匹配項的下標是 0 ，所以返回 0 。
示例 2：
輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現，所以返回 -1 。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
l1, l2 = len(haystack), len(needle)
if (l2 > l1):
return -1
for i in range(0, l1 - l2 + 1):
if (haystack[i] != needle[0]):
continue
j = 0
while (j < l2 and haystack[i + j] == needle[j]):
j += 1
if (j == l2):
return i
return -1
判斷子序列#
給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。
字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩餘字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
進階：
如果有大量輸入的 S，稱作 S1, S2, ... , Sk 其中 k >= 10 億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？
示例 1：
輸入：s = "abc", t = "ahbgdc"
輸出：true
示例 2：
輸入：s = "axc", t = "ahbgdc"
輸出：false
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
print(s,t)
if(len(s) == 0 or s == t):
return True
for i in range(0,len(t)):
if(t[i] == s[0]):
return self.isSubsequence(s[1:],t[i+1:])
return False
兩數之和 II - 輸入有序數組#
給你一個下標從 1 開始的整數數組 numbers ，該數組已按 非遞減順序排列 ，請你從數組中找出滿足相加之和等於目標數 target 的兩個數。如果設這兩個數分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。
以長度為 2 的整數數組 [index1, index2] 的形式返回這兩個整數的下標 index1 和 index2。
你可以假設每個輸入 只對應唯一的答案 ，而且你 不可以 重複使用相同的元素。
你所設計的解決方案必須只使用常量級的額外空間。
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等於目標數 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等於目標數 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等於目標數 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
start = 0
end = len(numbers) - 1
while(start < end):
if(numbers[start] + numbers[end] == target):
return [start+1,end+1]
elif(numbers[start] + numbers[end] > target):
end -= 1
else:
start += 1
盛最多水的容器#
給定一個長度為 n 的整數數組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
** 說明：** 你不能傾斜容器。
示例 1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例 2：
輸入：height = [1,1]
輸出：1
class Solution:
def maxArea(self, height: list[int]) -> int:
start,end = 0,len(height)-1
res = (end-start) * min(height[start],height[end])
while(start < end):
if(height[start] < height[end]):
start += 1
else:
end -= 1
res = max(res,(end-start) * min(height[start],height[end]))
return res