587. Erect the Fence
龍大惡墮了，他把自己的仁慈與軟弱打包起來丟掉。
憂鬱龍大已經不存在，接下來，邊板與皇城就由我來統治（把頭髮往後梳）。
請幫龍大找出打包的方法，給你很多點，輸出他們的凸包。
Example 1:
https://assets.leetcode.com/uploads/2021/04/24/erect2-plane.jpg
Input: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[3,3],[2,4],[4,2]]
思路:
1.禮物打包問題，以前修計算幾何有學過，不過忘的差不多了，只記得是用斜率算
這題範圍很小可以直接記每個 x 座標上最高和最低的點
可以把上下分開算 也就是先用最高點算出上半部分的包裝 再用最低點算下半部分
2.如何算上半部分就是去 iterate x 的左界和右界 從左到右加入每個 x 的最高點
如果說連續 a, b, c 三個點 線段ab斜率 < 線段bc斜率 那就是說中間的 b 會凹下去
所以最後凸包上不會有 b 這個點 這裡就可以用老方法 維護一個 stack
每次有點 c 進來就檢查 stack[-2] stack[-1] 和 c 的關係
如果 stack[-1] 會凹下去就 pop 掉 最後 stack 中的那些點就是凸包
3.下半部分算法類似 分開算最後再把上下半部分併在一起就好
為了不重複可以用 set 記
Python code:
class Solution:
def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
yatx = defaultdict(list)
left, right = 101, 0
for x, y in trees:
insort(yatx[x], y)
left = min(left, x)
right = max(right, x)
def slope(a, b):
return (b[1]-a[1]) / (b[0]-a[0])
res = set()
for y in yatx[left]:
res.add((left, y))
for y in yatx[right]:
res.add((right, y))
maxstk = [(left, yatx[left][-1])]
minstk = [(left, yatx[left][0])]
for i in range(left+1, right+1):
if i in yatx:
while len(maxstk) > 1 and slope(maxstk[-2], (i, yatx[i][-1]))
< slope(maxstk[-1], (i, yatx[i][-1])):
maxstk.pop()
while len(minstk) > 1 and slope(minstk[-2], (i, yatx[i][0]))
> slope(minstk[-1], (i, yatx[i][0])):
minstk.pop()
maxstk.append((i, yatx[i][-1]))
minstk.append((i, yatx[i][0]))
res.update(maxstk)
res.update(minstk)
return list(res)

大師

謝謝 謝謝喔 我要去玩寶可夢了

笑死 大師