# [065] LeetCode 128 演算法【Longest Consecutive Sequence】最長連續序列

128. Longest Consecutive Sequence (Hard)

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

`Input: [100, 4, 200, 1, 3, 2]Output: 4Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.`

--

--

# [064] LeetCode 334演算法【Increasing Triplet Subsequence】遞增三元子序列

334. Increasing Triplet Subsequence (Medium)

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that
arr[i] < arr[j] < arr[k] given 0 ≤ i < j < kn-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

`Input: [1,2,3,4,5]Output: true`

Example 2:

`Input: [5,4,3,2,1]Output: false`

--

--

# [063] LeetCode 42 演算法【Trapping Rain Water】收集雨水

42. Trapping Rain Water (Hard)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

`Input: [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6`

1.雙指針

`1.跟原本的指針一樣高2.比原本指針低3.比原本指針高`

2.Stack

`1.丟入牆壁高度的index2.如果比棧內前一個值低的話入棧，空棧的話結束3.假設比前一個高的話，出棧並獲取當前棧頂元素(棧頂元素為低處會裝水)4.比對獲取的棧頂跟當前的棧差多少，並且乘以距離(當前-棧頂-1)5.指針往後移動`

3.DP

--

--

# [062] LeetCode 11 演算法【Container With Most Water】盛水最多的容器

11. Container With Most Water (Medium)

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

`Input: [1,8,6,2,5,4,8,3,7]Output: 49`

`1.只移動矮的，因為高的移動只會讓面積更小2.是用最矮的長度去相乘`

--

--

# [061] LeetCode 309演算法【Best Time to Buy and Sell Stock with Cooldown】 股票機器人擬人版

309. Best Time to Buy and Sell Stock with Cooldown (Medium)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

`Input: [1,2,3,0,2]Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]`

--

--

# [056] LeetCode 45演算法【Jump Game II】跳躍遊戲 II

45. Jump Game II (Hard)

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

`Input: [2,3,1,1,4]Output: 2Explanation: The minimum number of jumps to reach the last index is 2.Jump 1 step from index 0 to 1, then 3 steps to the last index.`

Note:

You can assume that you can always reach the last index.

--

--