-
Notifications
You must be signed in to change notification settings - Fork 0
/
84 Largest Rectangle in Histogram.rtf
41 lines (39 loc) · 3.78 KB
/
84 Largest Rectangle in Histogram.rtf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
{\rtf1\ansi\ansicpg1252\cocoartf2706
\cocoatextscaling0\cocoaplatform0{\fonttbl\f0\fnil\fcharset0 .SFNS-Regular_wdth_opsz120000_GRAD_wght1F40000;\f1\fnil\fcharset0 Menlo-Regular;\f2\fnil\fcharset0 HelveticaNeue;
}
{\colortbl;\red255\green255\blue255;\red29\green29\blue29;\red255\green255\blue255;\red12\green99\blue153;
\red0\green0\blue0;\red210\green50\blue85;\red135\green135\blue135;\red85\green138\blue3;\red135\green91\blue44;
\red255\green255\blue255;\red133\green0\blue67;\red93\green108\blue125;}
{\*\expandedcolortbl;;\cssrgb\c14902\c14902\c14902;\cssrgb\c100000\c100000\c100000;\cssrgb\c0\c46667\c66667;
\cssrgb\c0\c0\c0;\cssrgb\c86667\c29020\c40784;\cssrgb\c60000\c60000\c60000;\cssrgb\c40000\c60000\c0;\cssrgb\c60392\c43137\c22745;
\cssrgb\c100000\c100000\c100000\c50196;\cssrgb\c60000\c0\c33333;\cssrgb\c43922\c50196\c56471;}
\margl1440\margr1440\vieww11520\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\partightenfactor0
\f0\fs36 \cf2 \cb3 \expnd0\expndtw0\kerning0
\outl0\strokewidth0 \strokec2 84\'a0Largest Rectangle in Histogram
\f1\fs26 \cf4 \cb1 \strokec4 \
\pard\pardeftab720\partightenfactor0
\cf4 class\cf0 \strokec5 \cf6 \strokec6 Solution\cf7 \strokec7 :\cf0 \strokec5 \
\cf4 \strokec4 def\cf0 \strokec5 \cf6 \strokec6 largestRectangleArea\cf7 \strokec7 (\cf0 \strokec5 self\cf7 \strokec7 ,\cf0 \strokec5 heights\cf7 \strokec7 :\cf0 \strokec5 List\cf7 \strokec7 [\cf8 \strokec8 int\cf7 \strokec7 ])\cf0 \strokec5 \cf9 \cb10 \strokec9 ->\cf0 \cb1 \strokec5 \cf8 \strokec8 int\cf7 \strokec7 :\cf0 \strokec5 \
stack \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 \cf7 \strokec7 []\cf0 \strokec5 \
maxArea \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 \cf11 \strokec11 0\cf0 \strokec5 \
\
\cf4 \strokec4 for\cf0 \strokec5 i\cf7 \strokec7 ,\cf0 \strokec5 h \cf4 \strokec4 in\cf0 \strokec5 \cf8 \strokec8 enumerate\cf7 \strokec7 (\cf0 \strokec5 heights\cf7 \strokec7 ):\cf0 \strokec5 \
start \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 i\
\cf4 \strokec4 while\cf0 \strokec5 stack \cf4 \strokec4 and\cf0 \strokec5 stack\cf7 \strokec7 [\cf9 \cb10 \strokec9 -\cf11 \cb1 \strokec11 1\cf7 \strokec7 ][\cf11 \strokec11 1\cf7 \strokec7 ]\cf9 \cb10 \strokec9 >\cf0 \cb1 \strokec5 h\cf7 \strokec7 :\cf0 \strokec5 \
stackIndex\cf7 \strokec7 ,\cf0 \strokec5 stackheight \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 stack\cf7 \strokec7 .\cf0 \strokec5 pop\cf7 \strokec7 ()\cf0 \strokec5 \
maxArea \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 \cf8 \strokec8 max\cf7 \strokec7 (\cf0 \strokec5 maxArea\cf7 \strokec7 ,\cf0 \strokec5 stackheight \cf9 \cb10 \strokec9 *\cf0 \cb1 \strokec5 \cf7 \strokec7 (\cf0 \strokec5 i\cf9 \cb10 \strokec9 -\cf0 \cb1 \strokec5 stackIndex\cf7 \strokec7 ))\cf0 \strokec5 \
start \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 stackIndex\
stack\cf7 \strokec7 .\cf0 \strokec5 append\cf7 \strokec7 ((\cf0 \strokec5 start\cf7 \strokec7 ,\cf0 \strokec5 h\cf7 \strokec7 ))\cf0 \strokec5 \
\
\cf12 \strokec12 #for remaining elements in stack\cf0 \strokec5 \
\cf4 \strokec4 print\cf7 \strokec7 (\cf0 \strokec5 maxArea\cf7 \strokec7 )\cf0 \strokec5 \
\
\cf4 \strokec4 for\cf0 \strokec5 i\cf7 \strokec7 ,\cf0 \strokec5 h \cf4 \strokec4 in\cf0 \strokec5 stack\cf7 \strokec7 :\cf0 \strokec5 \
maxArea \cf9 \cb10 \strokec9 =\cf0 \cb1 \strokec5 \cf8 \strokec8 max\cf7 \strokec7 (\cf0 \strokec5 maxArea\cf7 \strokec7 ,(\cf0 \strokec5 h\cf9 \cb10 \strokec9 *\cf7 \cb1 \strokec7 (\cf8 \strokec8 len\cf7 \strokec7 (\cf0 \strokec5 heights\cf7 \strokec7 )\cf9 \cb10 \strokec9 -\cf0 \cb1 \strokec5 i\cf7 \strokec7 )))\cf0 \strokec5 \
\
\cf4 \strokec4 return\cf0 \strokec5 maxArea\
\pard\pardeftab560\slleading20\partightenfactor0
\f2 \cf0 \kerning1\expnd0\expndtw0 \outl0\strokewidth0 \
}