Approach 1: Square by Square
Let's try to count the surface area contributed by
v = grid[i][j].
v > 0, the top and bottom surface contributes an area of 2.
Then, for each side (west side, north side, east side, south side) of the column at
grid[i][j], the neighboring cell with value
nv means our square contributes
max(v - nv, 0).
For example, for
grid = [[1, 5]], the contribution at
grid is 2 + 5 + 5 + 5 + 4. The 2 comes from the top and bottom side, the 5 comes from the north, east, and south side; and the 4 comes from the west side, of which 1 unit is covered by the adjacent column.
v = grid[r][c] > 0, count
ans += 2, plus
ans += max(v - nv, 0) for each neighboring value
nv adjacent to
Time Complexity: , where is the number of rows (and columns) in the
Space Complexity: .
Analysis written by: @awice.