Pythonで最大の三角形の領域
平面上の点のリストがあるとします。 3つの点で形成できる最大の三角形の領域を見つける必要があります。
したがって、入力が[[0,0]、[0,1]、[1,0]、[0,2]、[2,0]]の場合、出力は2
になります。
これを解決するには、次の手順に従います-
- res:=0
- N:=ポイントリストのサイズ
- 0からN-2の範囲のiの場合、do
- i +1からN-1の範囲のjの場合、do
- i + 2からNの範囲のkについては、
- (x1、y1):=points [i]、
- (x2、y2):=points [j]、
- (x3、y3):=ポイント[k]
- res:=resの最大値、0.5 * | x1 *(y2-y3)+ x2 *(y3-y1)+ x3 *(y1-y2)
- i + 2からNの範囲のkについては、
- i +1からN-1の範囲のjの場合、do
- return res
理解を深めるために、次の実装を見てみましょう-
例
class Solution: def largestTriangleArea(self, points): res = 0 N = len(points) for i in range(N - 2): for j in range(i + 1, N - 1): for k in range(i + 2, N): (x1, y1), (x2, y2), (x3, y3) = points[i],points[j],points[k] res = max(res, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))) return res ob = Solution() print(ob.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]))
入力
[[0,0],[0,1],[1,0],[0,2],[2,0]]
出力
2.0
-
Pythonのヒストグラムの下で最大の長方形の領域を見つけるプログラム
ヒストグラムの棒の高さを表す数値のリストがあるとします。バーの下に形成できる最大の長方形の領域を見つける必要があります。 したがって、入力がnums =[3、2、5、7]のような場合 その場合、出力は10になります これを解決するには、次の手順に従います- stk:=スタックで、最初に-1を挿入します 高さの最後に0を挿入 ans:=0 0から高さのサイズまでの範囲のiについては、 heights [i]
-
Pythonのヒストグラムで最大の長方形
ヒストグラムの高さを表す整数配列が1つあるとします。各バーには単位幅があります。次のように最大面積の長方形を見つける必要があります- これを解決するには、次の手順に従います- スタックを作成し、i:=0、ans:=0を設定します <高さのサイズなら スタックの要素が0であるか、スタックの最上位要素の高さが<=height [i]の場合、 iをスタックに挿入し、iを1増やします それ以外の場合- x:=スタックの最上位要素、スタックから削除します。 height:=heights [x] temp:=height *(i * stac