forked from daiwb/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBestView.html
More file actions
3 lines (3 loc) · 4.2 KB
/
BestView.html
File metadata and controls
3 lines (3 loc) · 4.2 KB
1
2
3
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>There are several skyscrapers arranged in a row. You're interested in finding the one from which the maximal number of other skyscrapers can be seen. The i-th skyscraper can be represented as a line segment on a plane with endpoints (i, 0) and (i, <b>heights</b>[i]). A skyscraper can be seen from the roof of another skyscraper if a line segment connecting their roofs does not intersect with or touch any other skyscraper. Return the maximal number of other skyscrapers that can be seen from the roof of some skyscraper.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>BestView</td></tr><tr><td>Method:</td><td>numberOfBuildings</td></tr><tr><td>Parameters:</td><td>vector <int></td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int numberOfBuildings(vector <int> heights)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>heights</b> will contain between 1 and 50 elements, inclusive. <br></br></td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>heights</b> will be between 1 and 1,000,000,000, inclusive.<br></br></td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{10}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2">There's only a single skyscraper, so you can see no other skyscrapers from its roof.
</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{5,5,5,5}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="2">From each skyscraper, you can only see its adjacent neighbors.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1,2,7,3,2}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 4</pre></td></tr><tr><td><table><tr><td colspan="2">You can see all the other skyscrapers from the central one.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1,5,3,2,6,3,2,6,4,2,5,7,3,1,5}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 7</pre></td></tr><tr><td><table><tr><td colspan="2"><p>You can see seven skyscrapers from the skyscraper with height 7:</p>
<p><img src="http://www.topcoder.com/contest/problem/BestView/ex3.gif"></img></p></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1000000000,999999999,999999998,999999997,999999996,1,2,3,4,5}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 6</pre></td></tr><tr><td><table><tr><td colspan="2">You can see 6 skyscrapers from the skyscraper with height 999999996 - the nearest one to the left and all 5 skyscrapers to the right.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{244645169,956664793,752259473,577152868,605440232,569378507,111664772,653430457,454612157,397154317}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 7</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>