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 < k ≤ n-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】收集雨水

下一篇：[065] LeetCode 128 演算法【Longest Consecutive Sequence】最長連續序列

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

這題有三種解法，雙指針、Stack、DP，相信有跟著我文章的朋友應該依看到這題目就可以想到能用DP去處理，我們先講雙指針的部分。

1.雙指針

這題思路很簡單，我們現在我們開兩個指針去做，左右兩邊我們先抓出兩邊最高的那一個地方，抓到以後指針往中間移動，只移動低的指針，接下來移動過程中我們判斷當下的地區可能有幾種情況：

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

計算水的公式為找出兩邊最低點並以(某一邊最高－某一邊目前高度)，因為水位是要用某邊最高高度去算，我們直接看代碼：

2.Stack

如果仔細看圖的話可以看出規律，藍色水外面一定是黑色的牆壁，這就剛好符合Stack這個資料結構，我們IDE的語法器就是用Stack去判斷的，判斷是否有把誇號打完就是利用Stack這個資料結構。

我們今天要做的事情很簡單：

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

3.DP

動態規劃的前提就是最佳子結構，無後效性，然後想辦法把上一次結果存起來，以我們這題來看的話，其實可以直接關注水滴左右兩旁的柱子高度就可以，最低柱子高度乘以比最低柱子高度更低的長度就會是水滴長度，有點繞口，我們可以使用兩個Array先記錄起從左邊開始看的高度成長以及從後邊開始看的高度成長，接下來我們再去取兩Array中最小的部分跟當下比對，我們直接看代碼：

大家加油。

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

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

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

這題思路很簡單，使用雙指針去判斷，我們用雙層回圈也可以做到這件事情，題目是找出最大面積，假設現在兩個都是7的話他就會是7*7=49，我們先釐清一下一些定義：

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

大家加油。

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

下一篇：[063] LeetCode 42 演算法【Trapping Rain Water】收集雨水

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]

這題跟上一題完全一模一樣，只是把條件變成前一天而已，因為至少暫停一天交易。

大家加油。

上一篇：[060] LeetCode 188演算法【Best Time to Buy and Sell Stock IV】 股票機器人 IV

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

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: 2
Explanation: 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.

這一題是上一題的follow up，差別在於要找到跳最小的步數，這題一樣可以用貪心法去解，在過程中記錄能走最遠的步數就可以。

大家加油。

上一篇：[055] LeetCode 55演算法【Jump Game】 跳躍遊戲

下一篇：[057] LeetCode 121 演算法【Best Time to Buy and Sell Stock】 股票機器人