{"id":185745,"date":"2020-10-21T15:06:16","date_gmt":"2020-10-21T07:06:16","guid":{"rendered":"http:\/\/4563.org\/?p=185745"},"modified":"2020-10-21T15:06:16","modified_gmt":"2020-10-21T07:06:16","slug":"%e7%ae%97%e6%b3%95%e9%a2%98-%e5%af%bb%e6%89%be-mountainarray-%e7%9a%84-peek-%e6%b1%82%e8%a7%a3%e6%83%91","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=185745","title":{"rendered":"\u7b97\u6cd5\u9898 \u5bfb\u627e MountainArray \u7684 peek \u6c42\u89e3\u60d1"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  \u7b97\u6cd5\u9898 \u5bfb\u627e MountainArray \u7684 peek \u6c42\u89e3\u60d1               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : amiwrong123 <\/span>  <span><i><\/i> 7<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<p>\u5176\u5b9e\u8fd9\u4e2a\u9898\u662f https:\/\/leetcode-cn.com\/problems\/find-in-mountain-array\/ \u7684\u4e00\u90e8\u5206\uff1a \u6bd4\u5982\uff0carray = [1,2,3,4,5,3,1]\uff0c\u8fd9\u4e2a\u6570\u7ec4\u662f\u7531\u4e25\u683c\u9012\u589e\u548c\u4e25\u683c\u9012\u51cf\u7684\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u6784\u6210\u7684\uff0c\u5b83\u7684 peek \u5c31\u662f 5. \u73b0\u5728\u6211\u6539\u4e00\u4e0b\u6761\u4ef6\uff0c\u8981\u4e48\u8fd9\u4e2a\u6570\u7ec4\u662f\u4e25\u683c\u9012\u589e\u548c\u4e25\u683c\u9012\u51cf\u7684\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u6784\u6210\u7684\uff08\u8fd9\u79cd\u60c5\u51b5\u8fd4\u56de peek \u7684\u7d22\u5f15\uff09\uff0c\u8981\u4e48\u8fd9\u4e2a\u6570\u7ec4\u5c31\u53ea\u662f\u4e00\u4e2a\u4e25\u683c\u9012\u589e\u6216\u4e25\u683c\u9012\u51cf\u7684\u6570\u7ec4\uff08\u8fd4\u56de-1 \uff09\u3002<\/p>\n<p>\u5f88\u660e\u663e\uff0c\u5bfb\u627e peek \u53ef\u4ee5\u7528\u4e8c\u5206\u67e5\u627e\u3002<\/p>\n<p>\u7136\u540e\u6211\u53d1\u73b0\u8fd9\u4e2a\u7b97\u6cd5\u6709\u4e24\u79cd\u5199\u6cd5\uff1a<\/p>\n<pre><code>    public int findArrayPeek(int[] array) {         int low = 0, high = array.length-1;          int middle = -1;         while (low &lt;= high &amp;&amp; (middle = (low + high)\/2)-1 &gt; 0 &amp;&amp; middle+1 &lt; array.length) {             if (array[middle-1] &lt; array[middle] &amp;&amp; array[middle] &gt; array[middle+1]) {                 return middle;             } else if (array[middle-1] &lt; array[middle] &amp;&amp; array[middle] &lt; array[middle+1]) {                 low = middle+1;             } else {                 high = middle-1;             }         }          return -1;     }      @Test     public void findArrayPeekTest() {         int[] array = {1,2,3,4,5,3,1};         System.out.println(findArrayPeek(array));         int[] array1 = {0,1,2,4,2,1};         System.out.println(findArrayPeek(array1));         int[] array2 = {0,1,2,4,5,1};         System.out.println(findArrayPeek(array2));         int[] array3 = {0,1,2,4,5,6};         System.out.println(findArrayPeek(array3));         int[] array4 = {6,5,4,3,2,1};         System.out.println(findArrayPeek(array4));     } <\/code><\/pre>\n<p>\u9996\u5148\u662f\u6807\u51c6\u7684\u4e8c\u5206\u67e5\u627e\uff0c\u4f46\u5faa\u73af\u6761\u4ef6\u4e2d\u5fc5\u987b\u8981\u4e0a\u7d22\u5f15\u7684\u4fdd\u62a4\u3002<\/p>\n<pre><code>    public int findArrayPeek1(int[] array) {         int low = 0, high = array.length-1;                  while (low &lt; high-1) {             int middle = (low + high)\/2;             if (array[middle-1] &lt; array[middle] &amp;&amp; array[middle] &gt; array[middle+1]) {                 return middle;             } else if (array[middle-1] &lt; array[middle] &amp;&amp; array[middle] &lt; array[middle+1]) {                 low = middle;             } else {                 high = middle;             }         }          return -1;     }      @Test     public void findArrayPeek1Test() {         int[] array = {1,2,3,4,5,3,1};         System.out.println(findArrayPeek1(array));         int[] array1 = {0,1,2,4,2,1};         System.out.println(findArrayPeek1(array1));         int[] array2 = {0,1,2,4,5,1};         System.out.println(findArrayPeek1(array2));         int[] array3 = {0,1,2,4,5,6};         System.out.println(findArrayPeek1(array3));         int[] array4 = {6,5,4,3,2,1};         System.out.println(findArrayPeek1(array4));     } <\/code><\/pre>\n<p>\u7136\u540e\u662f\u53e6\u5916\u4e00\u79cd\u5199\u6cd5\u5982\u4e0a\uff0c\u5b83\u7684\u5904\u7406\u8fc7\u7a0b\u4ece<code>low = middle+1;<\/code>\u53d8\u6210\u4e86<code>low = middle;<\/code>\uff0c\u8fd9\u91cc\u5faa\u73af\u6761\u4ef6\u4e5f\u5fc5\u987b\u5f97\u53d8\uff0c\u4f46\u8fd9\u91cc\u4e0d\u7528\u52a0\u7d22\u5f15\u4fdd\u62a4\u3002<\/p>\n<p>\u8fd9\u4e24\u4e2a\u7b97\u6cd5\uff0c\u53d8\u5316\u7684\u53ea\u6709\u5bf9 low high \u7684\u5904\u7406\uff0c\u548c\u5faa\u73af\u6761\u4ef6\u3002\u4f46\u611f\u89c9\u539f\u7406\u6709\u70b9\u4e0d\u4e00\u6837\uff0c\u4f46\u6211\u53c8\u8bf4\u4e0d\u6e05\u695a\u3002\u3002\u3002\uff08\u8fd9\u79cd\u8bf4\u4e0d\u6e05\u695a\u7684\u611f\u89c9\uff0c\u5e94\u8be5\u662f\u6211\u6ca1\u6709\u5f7b\u5e95\u5f04\u61c2~\uff09<\/p>\n<p>\u6216\u8005\u8bf4\uff0c\u5bf9 low high \u7684\u5904\u7406\u600e\u4e48\u5f71\u54cd\u8fd9\u4e2a\u8fc7\u7a0b\u7684\uff0c\u76f8\u5e94\u7684\u5faa\u73af\u6761\u4ef6\u5e94\u8be5\u600e\u4e48\u5199\uff1f<\/p>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>5<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li data-pid=\"4005975\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : hitmanx <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             &#8220;\u8981\u4e48\u8fd9\u4e2a\u6570\u7ec4\u662f\u4e25\u683c\u9012\u589e\u548c\u4e25\u683c\u9012\u51cf\u7684\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u6784\u6210\u7684\uff08\u8fd9\u79cd\u60c5\u51b5\u8fd4\u56de peek \u7684\u7d22\u5f15\uff09\uff0c\u8981\u4e48\u8fd9\u4e2a\u6570\u7ec4\u5c31\u53ea\u662f\u4e00\u4e2a\u4e25\u683c\u9012\u589e\u6216\u4e25\u683c\u9012\u51cf\u7684\u6570\u7ec4\uff08\u8fd4\u56de-1 \uff09\u3002&#8221;<\/p>\n<p>\u6ca1\u770b\u660e\u767d\uff0c\u4f60\u589e\u52a0\u7684\u8fd9\u4e24\u79cd\u60c5\u51b5\u5934\u5c3e\u5224\u65ad\u4e00\u4e0b(O(1))\u5c31\u80fd\u77e5\u9053\u5427\uff0c\u6bd4\u5982<br \/>For A[n], n &gt;= 3,<br \/>if A[1] &gt; A[0]:<br \/>&#8230;.if A[n-2] &gt; A[n-1]: MoutainArray<br \/>&#8230;.else: \u5355\u8c03\u9012\u589e<br \/>else: \u5355\u8c03\u9012\u51cf                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4005976\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u4e3b<\/span> <span>\u8cc7\u6df1\u5927\u4f6c : amiwrong123 <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @hitmanx <br \/>\u90a3\u5565\uff0c\u4f60\u5f97\u8fd4\u56de peek \u7684\u7d22\u5f15\u5440\uff0c\u4f60\u8fd9\u6837\u53ea\u662f\u5224\u65ad\u8fd9\u662f\u54ea\u79cd\u6570\u7ec4\u3002\u3002\u5728\u8fd9\u9053 LeetCode \u9898\u91cc\u9762\uff0c\u4e5f\u662f\u5148\u9700\u8981\u83b7\u5f97 peek \u7684\u7d22\u5f15\u7684\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4005977\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : hitmanx <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @amiwrong123 \u6211\u7684\u610f\u601d\u662f\u6309\u7167\u6211\u7684\u7406\u89e3\uff0c\u4f60\u589e\u52a0\u7684\u989d\u5916\u51e0\u79cd\u60c5\u51b5\uff0c\u5176\u5b9e\u4e00\u4e2a O(1)\u7684\u5224\u65ad\u5c31\u5b8c\u6210\u4e86\uff0c\u5269\u4e0b\u7684\u53c8\u56de\u5230\u4e86\u539f\u6765\u7684\u9898\u76ee\uff0c\u6240\u4ee5\u5e76\u6ca1\u6709\u7ed9\u9898\u76ee\u5e26\u6765\u4efb\u4f55\u5b9e\u9645\u7684\u53d8\u5316\uff0c\u6bd4\u5982:<\/p>\n<p>if (A[1] &lt; A[0]):<br \/>&#8230;. return -1 # monotone decreasing<\/p>\n<p>if (A[n-2] &lt; A[n-1]):<br \/>&#8230;. return -1 # monotone increasing<\/p>\n<p>\/\/ same old code that finds the index within a mountain array                                                            <\/p><\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4005978\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u4e3b<\/span> <span>\u8cc7\u6df1\u5927\u4f6c : amiwrong123 <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             @hitmanx <br \/>\u597d\u5427\uff0c\u61c2\u4f60\u610f\u601d\u5566\u3002\u786e\u5b9e\u662f\u8fd9\u6837\u7684\uff0c\u76f8\u5f53\u4e8e\u4f60\u63d0\u524d\u5224\u65ad\u7279\u6b8a\u60c5\u51b5\uff0c\u7136\u540e\u5c31\u4e0d\u7528\u6267\u884c\u4e8c\u5206\u67e5\u8be2\u4ee3\u7801\u4e86\u3002\u4e0d\u8fc7\u6211\u91cd\u70b9\u8fd8\u662f\u5728\u4e8e\u8fd9\u4e2a\u4e8c\u5206\u67e5\u627e\u7684\u5199\u6cd5                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li data-pid=\"4005979\" data-uid=\"2\">\n<div>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : binux <\/span>  <\/div>\n<div> <i title=\"\u5f15\u7528\"><\/i>  <span>          <\/span> <\/div>\n<\/p><\/div>\n<div>                                                             \u539f\u7406\u6ca1\u6709\u4e0d\u4e00\u6837\u554a\uff0c\u5c31\u662f\u8fb9\u754c\u5904\u7406\u7ec6\u8282\u4e0d\u540c\u7f62\u4e86\u3002<br \/>\u4e8c\u5206\u672c\u6765\u5c31\u662f\u6709\u201c\u81ea\u9002\u5e94\u6027\u201d\u7684\uff0c\u53ea\u8981\u8d8b\u52bf\u548c\u7ec8\u7ed3\u6761\u4ef6\u662f\u5bf9\u7684\uff0c\u8fb9\u754c\u591a\u4e00\u4e2a\u5c11\u4e00\u4e2a\u6ca1\u6709\u5173\u7cfb\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>\u7b97\u6cd5\u9898 \u5bfb\u627e MountainAr&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/185745"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=185745"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/185745\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=185745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=185745"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=185745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}