How can I do culling in top-down (Zelda like) tile map?

[Elias Daler]

Here are some pictures for better understanding of culling problem

There are two ways of storing tiles in top-down games. One ("Flat") is to store it as it is seen, manually putting all the tiles to create illustion of height.
Another one ("3d") is what I'm doing right now. It's greatly simplified for brevity, so in this example I just specify the height of cells on the map. So the "1" in array tells us that the block is one tile high. Drawing is a bit trickier, because I have to draw "top" of the tile automatically, but it's pretty easy: I just draw it if it's the last one in the column.

And here are where culling problem starts...
Suppose that the player can only see what's inside the red rectangle:

Culling with "flat" way of storing map is easy, you just draw all tiles which intersect the viewport.
But it's not so easy with "3d" way, because you have to manually check if there are some high tiles below the viewport some part of which can be seen.
One obvious solution would be to find the biggest height on the map (let's call it Z_max) and then check Z_max tile rows below the lowest visible tile row to see if there are some visible tile columns.
But this seems like a waste of time, because there might be just several really high columns while the level will be mostly flat, so it won't be very efficient to look Z_max rows down every time.
So, what's the easier way to do culling in this scenario?

[Laurent]

With the way your map is designed, is it possible to store extra data in tiles? The idea would be that visible tiles can directly inform if they are overlapped by some other tiles with higher Z. This way you would still get all the required information by iterating over the visible tiles only.

[Ungod]

My first idea is similar to laurents. I think the most efficient way to solve this is storing additional information in tiles. Otherwise solutions will always have to iterate over non-visible tiles.

So lets say we've got a tile X with height 3. So why not just store a pointer to that tile in the 3 tiles above?
You'll have to consider the case that the pointer of some of those tiles already points to another previously created tile. Simply override it in this case, if the new tiles lies below the stored tile.

During rendering you can just draw the stored pointer instead of the tile itself (if I get your examples right).

Something like that.