title: Getting the number of "friend" tower
body: <p>Given <code>n</code> towers numbered 1, 2, 3,...,n, with their height (<code>h[i] = towers[i]</code> 's height) and a number k. </p>
  
  <p>Two tower <em>a, b</em> are considered friends iff:</p>
  
  <ul>
  <li>a - b = k</li>
  <li>h[a] == h[b]</li>
  <li>max(h[a+1], h[a+2] ... h[b - 1]) &lt;= h[a] </li>
  </ul>
  
  <p>How many `friendships' are there ?</p>
  
  <p>Solution is straight forward: </p>
  
  <pre><code>for i = 1, 2, 3, 4, 5, ..., n - k:
      if h[i] == h[i+k]:
          for j in range[i, i+k] :
               MAX = max(MAX, h[j]
          if MAX &lt;= h[i]:
               ans++
  </code></pre>
  
  <p>But I want the solution in the most efficient way. Please help.</p>
  
  <p>For a large <code>n</code>, the program will eat the RAM; to reduce that, instead of array I used a queue to add the height of towers (when q.size() == k, Just q.pop() ) . Checking for 3rd condition with a large k with naive solution must take time.</p>